We are given a list schedule of employees, which represents the working time for each employee.
Each employee has a list of non-overlapping Intervals, and these intervals are in sorted order.
Return the list of finite intervals representing common, positive-length free time for all employees, also in sorted order.
(Even though we are representing Intervals in the form [x, y], the objects inside are Intervals, not lists or arrays. For example, schedule[0][0].start = 1, schedule[0][0].end = 2, and schedule[0][0][0] is not defined). Also, we wouldn't include intervals like [5, 5] in our answer, as they have zero length.
Example 1:
Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]] Output: [[3,4]] Explanation: There are a total of three employees, and all common free time intervals would be [-inf, 1], [3, 4], [10, inf]. We discard any intervals that contain inf as they aren't finite.
Example 2:
Input: schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]] Output: [[5,6],[7,9]]
Constraints:
1 <= schedule.length , schedule[i].length <= 500 <= schedule[i].start < schedule[i].end <= 10^8Problem Overview: Each employee has a sorted list of non-overlapping working intervals. The goal is to return all finite intervals where every employee is simultaneously free. In practice, you need to combine multiple schedules and detect the gaps between merged working intervals.
Approach 1: Brute Force Flatten + Sort (O(N log N) time, O(N) space)
Collect every interval from every employee into a single list. Sort the intervals by start time using a standard sorting step. Then iterate through the sorted intervals while maintaining the latest merged end time. If the next interval starts after the current end, that gap represents a block of shared free time. This approach works because once intervals are globally ordered, detecting gaps becomes a simple linear scan.
Approach 2: Interval Merging (O(N log N) time, O(N) space)
This is the most common implementation. Flatten all intervals, sort by start time, and merge overlapping intervals using the classic array-based interval merging pattern. Maintain a merged interval list and extend the current interval whenever overlaps occur. After merging, iterate through the merged list and return the gaps between consecutive intervals. The key insight: free time appears only between merged busy intervals shared across all employees.
Approach 3: K-Way Merge with Min Heap (O(N log K) time, O(K) space)
Instead of flattening everything, treat each employee schedule as a sorted stream and perform a k-way merge using a heap (priority queue). Push the first interval from each employee into a min-heap keyed by start time. Repeatedly pop the earliest interval and track the maximum end time seen so far. If the next interval starts after that end, you found a shared free slot. Then push the next interval from the same employee into the heap. This reduces sorting cost because the heap only manages K employees at once.
Recommended for interviews: The interval merging approach is typically expected. It shows you recognize the classic "merge intervals" pattern and can apply it after flattening schedules. Mentioning the heap-based k-way merge demonstrates deeper knowledge of multi-stream merging and improves scalability when many employees are involved. Starting with the brute-force flattening idea shows understanding, but the optimized merging or heap approach signals strong algorithmic reasoning.
We can merge all employees' working time intervals into a single list, then sort and merge the overlapping intervals. Finally, we traverse the merged interval list to find the free time periods between adjacent intervals.
The time complexity is O(mn log(mn)) and the space complexity is O(mn), where m is the number of employees and n is the number of working intervals per employee.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Flatten + Sort | O(N log N) | O(N) | Simple implementation when total intervals are manageable |
| Interval Merging | O(N log N) | O(N) | General case and most common interview solution |
| K-Way Merge with Heap | O(N log K) | O(K) | Large number of intervals but relatively few employees |
EMPLOYEE FREE TIME (Leetcode) - Code & Whiteboard • babybear4812 • 10,598 views views
Watch 9 more video solutions →Practice Employee Free Time with our built-in code editor and test cases.
Practice on FleetCode