DSA problem
Employee Free Time
We are given a list schedule of employees, which represents the working time for each employee. Each employee has a list of non-overlapping Interval objects which are sorted by start time. Return the list of finite intervals representing common, positive-length free time for ALL employees, also in sorted order. Both interval start and end times can be any positive integer, but the returned intervals must have strictly positive length (start strictly less than end).
The intuition is that "common free time" is the complement of "any employee is working" within the time window covered by the schedules. If we union every employee's intervals into a single set of merged busy intervals, then the gaps between consecutive merged intervals are exactly the times during which nobody is working — i.e., the common free time.
The textbook line-sweep approach is to flatten all intervals from all employees into one combined list, sort by start time, and merge overlapping or touching intervals using a single sweep. After merging, the answer is the set of gaps between the end of merged interval i and the start of merged interval i + 1, for each adjacent pair. The first gap before the earliest start and the gap after the latest end are excluded because the problem asks only for finite gaps between busy windows.
This sort-and-merge solution runs in O(N log N) time where N is the total number of intervals across all employees, and O(N) space. There is also a more elegant O(N log K) heap-based solution that exploits the fact that each employee's intervals are already sorted, but the simple flatten-and-sort approach is the cleanest line-sweep formulation and is what we implement here.
Examples
schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]][[3,4]]schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]][[5,6],[7,9]]schedule = [[[1,5]],[[2,3]]][]Constraints
- 1 <= schedule.length, schedule[i].length <= 50
- 0 <= schedule[i].start < schedule[i].end <= 10^8
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.