Fewest Clips to Cover a Broadcast
Problem
A live broadcast ran from second 0 to second T. Several cameras recorded clips given as [start, end], and clips may overlap or run past T. Any clip can be trimmed. Return the fewest clips needed to cover the whole broadcast from 0 to T, or -1 if some moment is missing from every clip.
Examples
Input: clips = [[0, 2], [4, 6], [8, 10], [1, 9], [1, 5], [5, 9]], T = 10
Output: 3
Why: [0, 2], then [1, 9], then [8, 10]Input: clips = [[0, 1], [1, 2]], T = 5
Output: -1
Why: nothing was recorded after second 2Input: clips = [[0, 4]], T = 3
Output: 1
Why: edge case, one clip longer than the broadcast is simply trimmedHints
0 / 3
Only one fact about the clips starting at a given second matters: how far the longest of them reaches. Reduce the input to that first.
Now it looks like a jump game. Standing at the end of your current coverage, you must add another clip, and the best one is whichever clip starting at or before that point reaches the furthest.
Record the furthest end for each start second. Walk the seconds from 0 to T - 1, tracking the furthest end reachable so far. Whenever you reach the end of the current coverage, add a clip and extend coverage to that furthest end, and return -1 if the furthest end does not move past the current second.
Solution
This is the reach frontier from the jump game with clips in place of jumps. For every start second only the longest clip matters, so the clips collapse into one furthest end per second. The walk keeps the end of the covered stretch and the furthest end offered by any clip starting inside it. When the walk reaches the covered end, a new clip is unavoidable, and choosing the one that reaches furthest is safe because any other choice covers a prefix of what it covers. If the furthest end is not past the current second at that moment, no clip bridges the gap. Time is O(n + T) for n clips, and space is O(T).
def fewest_clips(clips, T):
furthest = [0] * (T + 1) # longest reach of a clip starting at each second
for start, end in clips:
if start <= T:
furthest[start] = max(furthest[start], end)
count = covered = frontier = 0
for t in range(T):
frontier = max(frontier, furthest[t])
if t == covered: # the current coverage runs out here
if frontier <= t: # no clip reaches past this second
return -1
count += 1
covered = frontier
return count
print(fewest_clips([[0, 2], [4, 6], [8, 10], [1, 9], [1, 5], [5, 9]], 10)) # -> 3
print(fewest_clips([[0, 1], [1, 2]], 5)) # -> -1
print(fewest_clips([[0, 4]], 3)) # -> 1Stuck on the idea rather than the code? Jump Game covers it.