Employee Free Time
Problem
Given a list schedule of employees' working time intervals, return the list of finite intervals representing common free time across all employees, excluding infinite intervals.
- 1 ≤ schedule.length ≤ 50
- 1 ≤ schedule[i].length ≤ 50
- 0 ≤ schedule[i][j].start < schedule[i][j].end ≤ 10⁸
Example
schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]][[3,4]]First, flatten all employee intervals into one list: [1,2], [5,6], [1,3], [4,10]. Sorting by start time yields [1,2], [1,3], [4,10], [5,6]. Merging overlapping intervals results in [1,3] and [4,10]. The gap between these merged intervals is [3,4], which is the common free time where no employee is working.
Approach
Straightforward Solution
A brute-force approach might check every pair of intervals across employees to find overlaps and gaps, resulting in O(n^2) complexity, which is inefficient for large inputs.
Core Observation
The problem reduces to merging all employees' working intervals into a single timeline and then identifying gaps between these merged intervals as common free time.
Path to Optimal
PreviewFlattening all intervals into one list and sorting them by start time allows a linear scan to merge overlapping intervals efficiently. Once merged, the gaps between consecutive merged intervals represent the common free time…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewCollect all intervals from all employees into one list, sort by start time, then iterate through the sorted list to merge overlapping intervals. Track the end of the last merged interval to detect gaps…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(n log n)
Flattening all intervals results in n total intervals. Sorting them takes O(n log n). The single pass merge scan is O(n), so overall complexity is dominated by sorting.
Space
O(n)
Storing all intervals in a single list requires O(n) space, where n is the total number of intervals across all employees. The output list of free intervals is at most O(n) but typically smaller.
Pattern Spotlight
Merge Intervals (Flatten and Merge)
When multiple sorted interval lists represent busy times, merging them into a single sorted list and scanning for gaps efficiently reveals common free time without complex pairwise comparisons.
Solution
| 1 | class Solution: |
| 2 | def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]': |
| 3 | intervals = [] |
| 4 | |
| 5 | for employee in schedule: |
| 6 | for interval in employee: |
| 7 | intervals.append(interval) |
| 8 | |
| 9 | intervals.sort(key=lambda x: x.start) |
| 10 | |
| 11 | res = [] |
| 12 | prev_end = intervals[0].end |
| 13 | |
| 14 | for i in range(1, len(intervals)): |
| 15 | start = intervals[i].start |
| 16 | end = intervals[i].end |
| 17 | |
| 18 | if start > prev_end: |
| 19 | res.append(Interval(prev_end, start)) |
| 20 | |
| 21 | prev_end = max(prev_end, end) |
| 22 | |
| 23 | return res |
Step-by-Step Solution
Flatten All Employee Intervals into a Single List
| 3 | intervals = [] |
| 5 | for employee in schedule: |
| 6 | for interval in employee: |
| 7 | intervals.append(interval) |
Objective
To combine all employees' working intervals into one list for unified processing.
Key Insight
By flattening the nested schedule structure, the problem reduces from multiple sorted lists to a single list of intervals. This simplification enables the use of a standard merge intervals approach, avoiding complex multi-list merging logic.
Interview Quick-Check
Core Logic
Flattening transforms the problem into a single sorted list of intervals, enabling efficient merging.
Common Pitfalls & Bugs
Forgetting to flatten all intervals before sorting leads to incorrect or inefficient merging.
Sort Intervals by Start Time to Prepare for Merging
To order intervals so that overlapping intervals are adjacent, enabling linear-time merging.
Iterate Through Sorted Intervals to Identify and Collect Free Time Gaps
To merge overlapping intervals and detect gaps between merged intervals as common free time.
Return the List of Common Free Time Intervals
To output the computed list of intervals representing common free time.
3 more steps with full analysis available on Pro.
Line Analysis
This solution has 4 Critical lines interviewers watch for.
if start > prev_end:Check if there is a gap between previous end and current start.
A gap (start > prev_end) indicates a free time interval where no employee is working.
intervals.sort(key=lambda x: x.start)Sort all collected intervals by their start time.
Sorting by start time arranges intervals so that overlapping intervals are adjacent, enabling efficient linear merging.
prev_end = intervals[0].endSet prev_end to the end of the first interval to track merged interval boundaries.
Tracking the end of the last merged interval is critical to detect gaps and merge overlaps correctly.
Full line-by-line criticality + rationale for all 14 lines available on Pro.
Test Your Understanding
Why does merging all intervals into one sorted list and scanning for gaps correctly identify common free time across all employees?
See the answer with Pro.
Related Problems
Merge Intervals pattern
Don't just read it. Drill it.
Reconstruct Employee Free Time from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Employee Free Time drill