1. Problem Statement
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 sorted in increasing order.
Return the list of finite intervals representing common, positive-length free time for all employees, also in sorted order.
Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]
2. Approach: Min-Heap (K-Way Merge)
Since each employee's schedule is already sorted, we can treat this as a "Merge K Sorted Streams" problem.
- Initialize: Use a Min-Heap to store the first interval of each employee. The heap should sort by the
starttime. - Iterate:
- While the heap is not empty:
- Pop the interval with the smallest start time.
- Check for a Gap: If
last_end_time < current_start_time, we've found common free time! - Add the gap
[last_end_time, current_start_time]to our result. - Update
last_end_time = max(last_end_time, current_end_time). - Push the next interval from the same employee into the heap.
- While the heap is not empty:
3. Java Implementation
public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
List<Interval> res = new ArrayList<>();
// Heap stores {EmployeeIndex, IntervalIndex}
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) ->
schedule.get(a[0]).get(a[1]).start - schedule.get(b[0]).get(b[1]).start);
for (int i = 0; i < schedule.size(); i++) {
pq.add(new int[]{i, 0});
}
int lastEnd = schedule.get(pq.peek()[0]).get(pq.peek()[1]).start;
while (!pq.isEmpty()) {
int[] top = pq.poll();
Interval curr = schedule.get(top[0]).get(top[1]);
if (lastEnd < curr.start) {
res.add(new Interval(lastEnd, curr.start));
}
lastEnd = Math.max(lastEnd, curr.end);
// Add next interval of the same employee
if (top[1] + 1 < schedule.get(top[0]).size()) {
pq.add(new int[]{top[0], top[1] + 1});
}
}
return res;
}
4. 5-Minute "Video-Style" Walkthrough
- The "Aha!" Moment: Common free time is just the Gap between the merged intervals of all employees.
- The Efficiency: We could just flatten all intervals and sort them ($O(N \log N)$). But because each employee's list is already sorted, using a heap ($O(N \log K)$) is faster when the number of employees $K$ is small.
- The Sentinel: We initialize
lastEndto the earliest start time. Any gap we find before processing an interval is a "global" gap where nobody is working.
5. Interview Discussion
- Interviewer: "What is the time complexity?"
- You: "It is $O(N \log K)$ where $N$ is the total number of intervals across all employees, and $K$ is the number of employees."
- Interviewer: "What if the intervals were not sorted?"
- You: "Then I would flatten them and use the standard $O(N \log N)$ Merge Intervals logic."