Loading page…
Practice problem · medium
A streaming app records a live show that lasts length seconds. Many cameras each saved a clip, a range of seconds [start, end]. Clips can overlap, and a clip may stop where another starts.
An editor wants to cover the whole show, from second 0 to second length, using as few clips as possible. Every moment of the show must be inside at least one chosen clip.
Write fewest_clips(clips, length).
clips[i] = [start, end], with start < end. A clip covers the time from start to end.length, with no gap.Input: clips = [[0, 4], [3, 9], [8, 12], [2, 6], [10, 15]], length = 15
Output: 4Keep the point covered so far. Among the clips that start at or before that point, take the one that reaches the furthest.
| Covered so far | Clips starting at or before it | Furthest end | Clips used |
|---|---|---|---|
| 0 | [0, 4] | 4 | 1 |
| 4 | [3, 9], [2, 6] | 9 | 2 |
| 9 | [8, 12] | 12 | 3 |
| 12 | [10, 15] | 15 | 4 |
Second 15 is reached with 4 clips.
Input: clips = [[0, 2], [4, 6]], length = 6
Output: -1Nothing covers the time between 2 and 4, so the show cannot be covered.
Input: clips = [[0, 5], [5, 10]], length = 10
Output: 2The first clip stops at 5 and the second starts at 5, so there is no gap. Two clips are enough.
0 ≤ clips.length ≤ 100,0000 ≤ start < end ≤ 1,000,000 (seconds)1 ≤ length ≤ 1,000,000Filling a table with the fewest clips for every second means about length × n steps, which is 10^11 here. Sorting the clips by start costs n log n, and one pass after it costs n.
fewest_clips · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.