NeetCode #849LC-759HardIntervals
← Back to All Problems#849 · #759 · Employee Free Time(员工空闲时间)
📌 Problem Statement & Constraints
You are given the working schedules of several employees as a list of lists of intervals
schedule[i], each sorted and disjoint. Return the list of finite intervals representing the common free time for all employees, sorted by start. Constraints: 1 <= schedule.length <= 50, 0 <= schedule[i].length <= 50, 0 <= start < end <= 10^8.💡 Core Algorithmic Approaches
- Collect every working interval from every employee into one list and sort by start.
- Merge them into a single set of busy blocks.
- The gaps between consecutive merged busy blocks are the times when everyone is free.
- Only finite gaps are reported, so the time before the first block and after the last are not included.
💻 Benchmark Python3 Implementation
class Solution:
def employeeFreeTime(self, schedule):
# each entry is an Interval with .start / .end attributes
intervals = []
for emp in schedule:
for iv in emp:
intervals.append((iv.start, iv.end))
intervals.sort()
res = []
end = intervals[0][1]
for s, e in intervals[1:]:
if s > end: # a gap exists -> everyone is free
res.append(Interval(end, s))
end = e
else:
end = max(end, e)
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(N log N) where N is the total number of intervals: the sort dominates.
💾 Space Complexity
O(N): the flattened interval list.
⚠️ Interview Pitfalls & Follow-ups
- Emitting the gaps before the first and after the last block: those are unbounded or outside the schedule and must be excluded.
- Using
s >= end: touching intervals are not a free gap, so the test is stricts > end. - Merging only adjacent employees: the intervals must be merged globally, not per employee.
- Assuming the merged result is sorted: sorting by start and merging preserves the order, so the gaps come out sorted.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.