494. Employee Free Time
You are handed the working calendars of a whole team. schedule is a list with one entry per employee, and each entry is that employee's list of busy intervals [start, end) — already sorted by start and non-overlapping within that employee.
Your job is to find when the entire team is free at the same time: return every interval of positive length during which no employee is busy, restricted to the span between the earliest busy moment and the latest one (the unbounded free time before everyone's first meeting and after everyone's last is not interesting and must not be reported).
Return the free intervals sorted by start time. Two busy intervals that merely touch (one ends exactly when another starts) do not create free time — zero-length gaps don't count.
Example 1:
Input: schedule = [[[1,2],[5,6]], [[1,3]], [[4,10]]]
Output: [[3,4]]
Explanation: Someone is busy over [1,3] (employees 1 and 2), and someone is busy over [4,10] (employees 1 and 3 cover it). The only moment nobody works is the gap [3,4].
Example 2:
Input: schedule = [[[1,3],[6,7]], [[2,4]], [[2,5],[9,12]]]
Output: [[5,6],[7,9]]
Explanation: Union of all busy time is [1,5], [6,7], [9,12]. The finite gaps between those blocks are [5,6] and [7,9]; the time before 1 and after 12 is unbounded and excluded.
Constraints:
- 1 ≤ schedule.length ≤ 50
- 1 ≤ schedule[i].length ≤ 50
- 0 ≤ start < end ≤ 10⁸
- Each employee's intervals are sorted by start and pairwise disjoint.
Hints:
An interval is team-free exactly when it lies inside no employee's busy interval — so the answer is just the gaps in the union of all busy intervals. Try flattening everything into one list first.
Sort all intervals by start and sweep with a single rolling value: the furthest end seen so far. When the next interval starts strictly beyond that end, you have found a gap. Remember max(end, t) — a later interval can be swallowed by an earlier long one.
Each employee's list is already sorted — you can avoid the global sort with a min-heap holding one pointer per employee (k-way merge), popping intervals in start order in O(N log E).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: schedule = [[[1,2],[5,6]], [[1,3]], [[4,10]]]
Expected output: [[3,4]]