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
Flattening 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. This approach leverages the classic merge intervals pattern to transform a multi-list problem into a single sorted list problem.
Optimal Approach
Collect 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. Whenever a gap is found (current interval start > previous end), record it as free time. Return the list of all such gaps.
Time
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
| 9 | intervals.sort(key=lambda x: x.start) |
Objective
To order intervals so that overlapping intervals are adjacent, enabling linear-time merging.
Key Insight
Sorting intervals by their start time ensures that any overlapping intervals appear consecutively. This property is essential for the classic merge intervals algorithm to work correctly in a single pass.
Interview Quick-Check
Core Logic
Sorting by start time is the prerequisite for linear merging of intervals.
Complexity
Sorting dominates the time complexity at O(n log n), where n is the total number of intervals.
Iterate Through Sorted Intervals to Identify and Collect Free Time Gaps
| 11 | res = [] |
| 12 | prev_end = intervals[0].end |
| 14 | for i in range(1, len(intervals)): |
| 15 | start = intervals[i].start |
| 16 | end = intervals[i].end |
| 18 | if start > prev_end: |
| 19 | res.append(Interval(prev_end, start)) |
| 21 | prev_end = max(prev_end, end) |
Objective
To merge overlapping intervals and detect gaps between merged intervals as common free time.
Key Insight
Tracking the end of the last merged interval allows detection of gaps when the current interval starts after this end. These gaps represent times when no employee is working. Updating the end to the maximum of current and previous intervals ensures correct merging of overlapping intervals.
Interview Quick-Check
Core Logic
Merging intervals by comparing current start with previous end identifies overlaps and gaps, enabling extraction of free time.
State & Boundaries
Initialize prev_end with the end of the first interval to set the baseline for comparisons.
Common Pitfalls & Bugs
Failing to update prev_end to the max of previous end and current end can cause missed or incorrect free intervals.
Return the List of Common Free Time Intervals
| 23 | return res |
Objective
To output the computed list of intervals representing common free time.
Key Insight
After merging and gap detection, the collected intervals represent all finite free times common to all employees, fulfilling the problem requirements.
Interview Quick-Check
Core Logic
Returning the collected free intervals completes the solution, providing the required output.
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.
prev_end = max(prev_end, end)Update prev_end to the maximum of current prev_end and current interval's end.
Updating prev_end ensures the merged interval correctly covers all overlapping intervals, preventing missed gaps.
intervals.append(interval)Append the current interval to the unified intervals list.
Collecting all intervals into one list is essential for sorting and merging to find common free time.
res.append(Interval(prev_end, start))Append the free time interval between prev_end and current start to the result list.
Recording the gap as a free interval captures the common free time segment required by the problem.
intervals = []Initialize an empty list to hold all intervals from all employees.
This list serves as the unified container for all intervals, enabling a single sorted merge process rather than handling multiple lists separately.
return resReturn the list of common free time intervals.
Returning the accumulated free intervals completes the solution, providing the final answer as required.
res = []Initialize the result list to store free time intervals.
This list accumulates all detected gaps between merged intervals, representing common free time.
for i in range(1, len(intervals)):Iterate over intervals starting from the second interval.
Starting from the second interval allows comparison with the previous merged interval to find gaps or overlaps.
for employee in schedule:Iterate over each employee's schedule in the input.
Accessing each employee's intervals is necessary to flatten the nested schedule structure into a single list.
for interval in employee:Iterate over each interval in the current employee's schedule.
This nested iteration ensures every interval from every employee is collected for merging.
start = intervals[i].startExtract the start time of the current interval.
The start time is used to determine if a gap exists between intervals.
end = intervals[i].endExtract the end time of the current interval.
The end time is used to update the merged interval boundary.
Test Your Understanding
Why does merging all intervals into one sorted list and scanning for gaps correctly identify common free time across all employees?
Because merging intervals consolidates all overlapping busy times into continuous blocks, any gap between these blocks is a time when no employee is working, representing common free time.
Related Problems
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