931. The Gaps When Everyone Is Free

k people each give their busy times as a list of intervals. Within one person's list the intervals are sorted by start and no two of them overlap. Different people's lists are unrelated.

Print every maximal stretch of POSITIVE length during which nobody is busy, lying between the earliest start and the latest end of everything given. Print one stretch per line as two integers, in increasing order. Print none if there is no such stretch, including when nobody has any busy time at all.

``` person A [1,2] [5,6], person B [1,3], person C [4,10] -> 3 4

person A [1,3] [6,7] -> 3 6

two people, both with no intervals at all -> none ```

## What most people try first

Pouring everything into one list, sorting it and merging works and costs O(N log N) for N intervals in all. That is a correct answer and it throws away the fact that each list is ALREADY SORTED.

## The method: a k-way merge with a running reach

A heap holding one interval from each list turns the N log N sort into an N log k merge, which is the same saving problem #866 makes.

h = min-heap of (start, end, list index, position), seeded with the first interval of every non-empty list reach = nothing yet while h is not empty: (s, e, i, j) = pop the smallest start if reach is set and s > reach: output the gap (reach, s) reach = max(reach, e) if list i has another interval after j: push it

reach is the furthest point covered by everything popped so far. A gap exists exactly when the next interval starts beyond it.

## Why it is correct

Intervals are popped in non-decreasing order of start, because each list is sorted and the heap holds each list's smallest unpopped interval.

Claim: when an interval starting at s is popped, reach is the right end of the union of all intervals starting before s, if that union is a single piece reaching that far, and every gap before s has already been printed.

If s <= reach, this interval extends or sits inside the current piece and reach grows to max(reach, e). If s > reach, nothing covers the open stretch from reach to s, because every interval popped so far ends at or before reach and every interval NOT yet popped starts at s or later. So exactly one gap is emitted and the piece restarts at s.

The gaps are emitted in increasing order because s is non-decreasing.

## The boundary that breaks a careless implementation

reach = max(reach, e), not reach = e. A short interval popped after a long one that already covers it would otherwise pull the reach backwards and invent a gap. The test where one person is busy [0, 10^9] and another is busy [5, 6] exists for this.

The gap must have positive length, so the condition is s > reach and never s >= reach. Two intervals that merely touch leave no gap.

An empty list contributes no seed. Trying to read its first interval is the usual crash, and with every list empty the heap starts empty and the answer is none.

## Overflow

Times run up to 10^9 and the only arithmetic is a comparison and a maximum, so 32-bit integers hold everything. There is no overflow here. What does need care is the sentinel for "reach not set yet": use a flag or a value below every legal start, not zero, since 0 is a legal time.

## Related problems

Problem #255 merges overlapping intervals from ONE unsorted list by sorting, and problem #1436 inserts into a single sorted list. Problem #1438 intersects TWO sorted lists with two pointers, which is the same sweep with k = 2 and the pointers standing in for the heap. This is the general case: k sorted lists, so the heap replaces the pointers, and the output is the complement of the union rather than the union itself.

## Cost

Time O(N log k) for N intervals in all. Space O(k) beyond the input.

Constraints - `1 ≤ k ≤ 1000` - `0 ≤ m`, and the total number of intervals is at most 100000. - `0 ≤ start < end ≤ 10^9` - Each person's intervals are sorted by start and do not overlap each other.