1024. Video Stitching
Description
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:
Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10 Output: 3 Explanation: We take the clips [0,2], [8,10], [1,9]; a total of 3 clips. Then, we can reconstruct the sporting event as follows: We cut [1,9] into segments [1,2] + [2,8] + [8,9]. Now we have segments [0,2] + [2,8] + [8,10] which cover the sporting event [0, 10].
Example 2:
Input: clips = [[0,1],[1,2]], time = 5 Output: -1 Explanation: We cannot cover [0,5] with only [0,1] and [1,2].
Example 3:
Input: clips = [[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6,7],[1,3],[4,7],[1,4],[2,5],[2,6],[3,4],[4,5],[5,7],[6,9]], time = 9 Output: 3 Explanation: We can take clips [0,4], [4,7], and [6,9].
Constraints:
1 <= clips.length <= 100
0 <= starti <= endi <= 100
1 <= time <= 100
Solutions
Solution 1: Greedy
Note that if there are multiple sub-intervals with the same starting point, it is optimal to choose the one with the largest right endpoint.
Therefore, we can preprocess all sub-intervals. For each position $i$, calculate the largest right endpoint among all sub-intervals starting at $i$, and record it in the array $last[i]$.
We define a variable mx
to represent the farthest position that can currently be reached, a variable ans
to represent the current minimum number of sub-intervals needed, and a variable pre
to represent the right endpoint of the last used sub-interval.
Next, we start enumerating all positions $i$ from $0$, using $last[i]$ to update mx
. If after updating, $mx = i$, it means that the next position cannot be covered, so the task cannot be completed, return $-1$.
At the same time, we record the right endpoint pre
of the last used sub-interval. If $pre = i$, it means that a new sub-interval needs to be used, so we add $1$ to ans
and update pre
to mx
.
After the traversal is over, return ans
.
The time complexity is $O(n+m)$, and the space complexity is $O(m)$. Where $n$ and $m$ are the lengths of the clips
array and the value of time
, respectively.
Similar problems:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|