220. Clip Stitching
A film editor has a pile of video clips, all cut from the same timeline. Each clip clips[i] = [start, end] covers the stretch of the timeline from second start to second end. Clips may overlap, and one clip may begin exactly where another ends.
The editor wants to stitch together some of the clips so that every moment between second 0 and second time is covered with no hole, even a tiny one. A clip that sticks out past the ends of that window is fine. Return the smallest number of clips needed, or -1 if no choice of clips can cover the whole window. With up to 100,000 clips and a window up to 100,000 seconds long, trying every second against every clip is far too slow.
Example 1
- Input:
- clips = [[0,4],[3,7],[6,12]], time = 10
- Output:
- 3
- Explanation:
The clip [0,4] starts the window. From there [3,7] reaches furthest, and then [6,12] passes second 10. Three clips are needed and none can be skipped.
Example 2
- Input:
- clips = [[1,5],[2,9]], time = 6
- Output:
- -1
- Explanation:
Nothing starts at second 0, so the very first moment is uncovered: -1.
Example 3
- Input:
- clips = [[0,3],[3,8],[2,5],[8,10],[1,2]], time = 10
- Output:
- 3
- Explanation:
[0,3], then [3,8] (it starts exactly where the first ends), then [8,10]: 3 clips.
Example 4
- Input:
- clips = [[0,50]], time = 20
- Output:
- 1
- Explanation:
One clip already covers the window, even though it extends beyond it.
Constraints
1 ≤ clips.length ≤ 105
0 ≤ start ≤ end ≤ 105
0 ≤ time ≤ 105
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)