Surveillance Footage III
Cameras produced footage clips, each covering a time interval [start, end]. Some of the window [0, T] may be unrecoverable. Return every sub-interval of [0, T] that no clip covers, as [start, end] pairs in order.
clips = [[1, 2], [5, 7]], T = 10 -> [[0, 1], [2, 5], [7, 10]] clips = [[0, 4], [3, 10]], T = 10 -> []
Clips arrive in any order and may overlap arbitrarily; touching clips such as [0, 2] and [2, 5] leave no gap.
Hints
Hint 1
Sort by start and track the farthest end seen so far, starting from 0.
Hint 2
Whenever a clip starts past that end, the space in between was never covered. Whatever is left after the last clip, up to T, is one more gap.