HardNo. 0759LeetCode Premium
Employee Free Time — LeetCode 759 Python Solution
- Pattern
- Heap / Priority Queue
- Topics
- Array, Sorting, Line Sweep, 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
"""
# 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 ansComplexity
- Time
- O(mn log(mn))
- Space · auxiliary
- O(mn)where m is the number of employees and n is the number of working intervals per employee
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.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0218 | The Skyline Problem | Hard |
| 0215 | Kth Largest Element in an Array | Medium |
| 0506 | Relative Ranks | Easy |
| 0912 | Sort an Array | Medium |
| 0973 | K Closest Points to Origin | Medium |
| 1094 | Car Pooling | Medium |
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.