Employee Free Time

Problem

Each employee has a working schedule: a list of closed intervals, sorted by start and pairwise non-overlapping, during which they are busy. You are given schedule, a list of such lists, one per employee. Find the free time shared by everyone: the finite gaps during which no employee is busy. Return them as a list of intervals sorted by start, excluding any gap of zero length and excluding the unbounded time before the first busy interval and after the last one.

Intervals are provided as objects with start and end attributes (an Interval class); return a list of Interval objects.

• Up to about fifty employees, each with up to about fifty busy intervals.
• Every interval's start and end are non-negative and fit comfortably in a normal int, with start < end.

Examples

• schedule = [[[2,3],[6,7]],[[2,4]],[[5,11]]] → [[4,5]]. Merging everyone's busy time gives [2,4] and [5,11]; the only gap is [4,5].
• schedule = [[[2,4],[7,8]],[[3,5]],[[3,6],[10,13]]] → [[6,7],[8,10]]. Busy time merges into [2,6], [7,8], [10,13].
• schedule = [[[2,6]],[[6,10]]] → []. The two blocks touch, so there is no gap.

Hints

1. A moment is free for everyone only if it is free for each employee. What does the union of all busy intervals tell you?
2. If you had all busy intervals in one sorted stream, how would you spot the gaps? Each employee's list is already sorted; how do you merge k sorted lists efficiently?
3. Min-heap k-way merge by start (one entry per employee), tracking the furthest end seen; a start beyond that end reveals a gap.