Surveillance Footage II
Cameras produced footage clips, each covering a time interval [start, end]. Return the clips themselves — a smallest set whose union covers the whole window [0, T] — or null when no set covers it. Any minimal set is accepted, in any order.
clips = [[0,2], [4,6], [8,10], [1,9], [1,5], [5,9]], T = 10 -> [[0,2], [1,9], [8,10]]
Clips arrive in any order and may overlap arbitrarily; touching clips such as [0, 2] and [2, 5] leave no hole.
Hints
Hint 1
Sort by start and grow a covered prefix. Among the clips that start at or before the covered point, pick the one reaching farthest — and keep a reference to it.
Hint 2
When the best candidate doesn't reach past the covered point, no set works: return null.