Given a list of schedules (each is a list of non-overlapping intervals sorted by start time), find the list of finite intervals representing the common free time of all employees.
Input: [[[1,3],[6,7]], [[2,4]], [[2,5],[9,12]]] → Output: [[5,6],[7,9]]
Merge all intervals from all employees. Find gaps between consecutive merged intervals.
- Collect all intervals from all employees into one list.
- Sort by start time.
- Merge overlapping intervals.
- Collect gaps between consecutive merged intervals.
import java.util.*;
class Solution {
public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
List<Interval> all = new ArrayList<>();
for (List<Interval> emp : schedule) all.addAll(emp);
all.sort((a,b) -> a.start - b.start);
List<Interval> merged = new ArrayList<>();
for (Interval iv : all) {
if (!merged.isEmpty() && iv.start <= merged.get(merged.size()-1).end)
merged.get(merged.size()-1).end = Math.max(merged.get(merged.size()-1).end, iv.end);
else merged.add(new Interval(iv.start, iv.end));
}
List<Interval> res = new ArrayList<>();
for (int i = 1; i < merged.size(); i++)
res.add(new Interval(merged.get(i-1).end, merged.get(i).start));
return res;
}
}
- Time Complexity: O(N log N) where N = total intervals
- Space Complexity: O(N)