Employee Free Time

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.

Example 1

Input: [[[1,3],[6,7]], [[2,4]], [[2,5],[9,12]]] → Output: [[5,6],[7,9]]

Solution Approach

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.

Java

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)