Employee Free Time
Hard · Intervals · Array · Heap · Sorting · Sweep Line
Problem
schedule[i] lists the busy blocks of employee i, each a pair [start, end]. One employee's blocks never overlap and are given in increasing order; blocks of different employees can overlap freely.
Return every stretch of time during which all employees are free, as [start, end] pairs in increasing order. Only finite stretches of positive length count: the open-ended time before the first block and after the last is left out, and two blocks that meet at the same moment (one ends at t, another starts at t) leave no gap.
On LeetCode the blocks are Interval objects with .start and .end; here they are plain two-element lists, in every language, so schedule[i][j][0] is a start and schedule[i][j][1] its end.
Examples
Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]] Output: [[3,4]]
Taken together the blocks cover 1 to 3 and 4 to 10. Between them, 3 to 4, nobody is busy. Before 1 and after 10 are open-ended, so they are not reported.
Input: schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]] Output: [[5,6],[7,9]]
The union of all blocks is 1 to 5, 6 to 7 and 9 to 12, which leaves two gaps.
Constraints
- 1 <= schedule.length <= 50
- 1 <= schedule[i].length <= 50
- 0 <= start < end <= 10^8
- each employee's blocks are sorted and do not overlap
Approaches
- Check every stretch between block edges — time O(N²), space O(N)
Follow-up
What if the calendars are too large to hold in memory, or arrive as live streams? The heap version only ever holds one block per person, so it works as a streaming k-way merge: it needs O(k) memory and emits each gap as soon as the next block arrives. And if you need times when *most* people are free rather than all, a merged union no longer carries enough information; count busy people with a sweep line instead (see the use case below).
Related problems
Start free on Cariara · Coding problems · System design studio
