Video Stitching
You are given a series of video clips from a sporting event that lasted time seconds. These video clips can be overlapping with each other and have varying lengths.
Each video clip is described by an array clips where clips[i] = [starti, endi] indicates that the ith clip started at starti and ended at endi.
We can cut these clips into segments freely.
- For example, a clip
[0, 7]can be cut into segments[0, 1] + [1, 3] + [3, 7].
Return the minimum number of clips needed so that we can cut the clips into segments that cover the entire sporting event [0, time]. If the task is impossible, return -1.
Example 1
0---2
4---6
8---10
1---------------9
1-------5
5-------9Input
clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10Output
3We take clips [0,2], [8,10], and [1,9], then cut [1,9] so the segments [0,2] + [2,8] + [8,10] cover [0,10].
Example 2
0-1 1-2
Input
clips = [[0,1],[1,2]], time = 5Output
-1We cannot cover [0,5] with only [0,1] and [1,2].
Constraints
- 1 <= clips.length <= 100
- 0 <= starti <= endi <= 100
- 1 <= time <= 100
Asked at 2 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.