How hard is LeetCode 759. Employee Free Time?

LeetCode 759. Employee Free Time is rated Hard on LeetCode.

What is the time complexity of LeetCode 759. Employee Free Time?

The Python solution on this page runs in O(mn \log(mn)).

What is the space complexity of LeetCode 759. Employee Free Time?

The Python solution on this page uses O(mn), where m is the number of employees and n is the number of working intervals per employee auxiliary space.

What topics does LeetCode 759. Employee Free Time cover?

LeetCode 759. Employee Free Time is tagged Array, Sorting, Line Sweep and Heap (Priority Queue) on LeetCode.

Is LeetCode 759. Employee Free Time a premium problem?

Yes. LeetCode 759. Employee Free Time is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Employee Free Time — LeetCode 759 Python Solution

HardLeetCode PremiumArraySortingLine SweepHeap (Priority Queue)

Problem: #759
Pattern: Heap / Priority Queue
Reading time: 4 min
Source: leetcode.com

The problem

We are given a list schedule of employees, which represents the working time for each employee. Each employee has a list of non-overlapping Intervals, and these intervals are in sorted order.

Example

Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]
Explanation: There are a total of three employees, and all common

Python solution

Python

"""
# Definition for an Interval.
class Interval:
    def __init__(self, start: int = None, end: int = None):
        self.start = start
        self.end = end
"""


class Solution:
    def employeeFreeTime(self, schedule: "[[Interval]]") -> "[Interval]":
        intervals = []
        for e in schedule:
            intervals.extend(e)
        intervals.sort(key=lambda x: (x.start, x.end))
        merged = [intervals[0]]
        for x in intervals[1:]:
            if merged[-1].end < x.start:
                merged.append(x)
            else:
                merged[-1].end = max(merged[-1].end, x.end)
        ans = []
        for a, b in pairwise(merged):
            ans.append(Interval(a.end, b.start))
        return ans

Complexity

Measure	Complexity
Time	O(mn \log(mn))
Space	O(mn), where m is the number of employees and n is the number of working intervals per employee auxiliary

Pattern: Heap / Priority Queue

Keep only the best k elements, or always pull the smallest, in log time. LeetCode 759. Employee Free Time is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Heap (Priority Queue).

The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 759. Employee Free Time?: LeetCode 759. Employee Free Time is rated Hard on LeetCode.
What is the time complexity of LeetCode 759. Employee Free Time?: The Python solution on this page runs in O(mn \log(mn)).
What is the space complexity of LeetCode 759. Employee Free Time?: The Python solution on this page uses O(mn), where m is the number of employees and n is the number of working intervals per employee auxiliary space.
What topics does LeetCode 759. Employee Free Time cover?: LeetCode 759. Employee Free Time is tagged Array, Sorting, Line Sweep and Heap (Priority Queue) on LeetCode.
Is LeetCode 759. Employee Free Time a premium problem?: Yes. LeetCode 759. Employee Free Time is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.