297. Employee Free Time

Flatten all intervals into one list, sort by start, merge overlapping ones, then gaps between merged intervals are the free time.

Approach

1. Flatten all employee intervals into a single list.
2. Sort by start time.
3. Merge overlapping intervals.
4. Gaps between consecutive merged intervals are the employee free time.

Complexity

• Time: O(n log n) where n is total number of intervals.
• Space: O(n) for the merged list.

import java.util.*;

class Solution {
    public List<int[]> employeeFreeTime(List<List<int[]>> schedule) {
        List<int[]> intervals = new ArrayList<>();
        for (List<int[]> emp : schedule) {
            for (int[] iv : emp) {
                intervals.add(iv);
            }
        }
        intervals.sort((a, b) -> a[0] - b[0]);

        List<int[]> merged = new ArrayList<>();
        merged.add(intervals.get(0));
        for (int i = 1; i < intervals.size(); i++) {
            int[] curr = intervals.get(i);
            int[] last = merged.get(merged.size() - 1);
            if (curr[0] <= last[1]) {
                last[1] = Math.max(last[1], curr[1]);
            } else {
                merged.add(curr);
            }
        }

        List<int[]> result = new ArrayList<>();
        for (int i = 1; i < merged.size(); i++) {
            result.add(new int[]{merged.get(i - 1)[1], merged.get(i)[0]});
        }
        return result;
    }
}