Video Stitching
MedPrompt
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 <= 1000 <= starti <= endi <= 1001 <= time <= 100
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses dynamic programming to solve the problem. We build a solution for the interval [0, time] by using solutions for smaller intervals [0, i] where i < time. We define dp[i] as the minimum number of clips required to cover the interval [0, i]. Our goal is to compute dp[time] by iteratively building up the dp table.
Algorithm
- Create an integer array
dpof sizetime + 1to store the minimum number of clips to cover the interval[0, i]. - Initialize
dp[0]to 0 and all other elementsdp[i]to a value representing infinity (e.g.,time + 2, which is larger than any possible valid answer). - Iterate
ifrom 1 totime. For eachi, we want to computedp[i]. - Inside this loop, iterate through all available clips
[start, end]. - If a clip can cover the time point
i(i.e.,start < i <= end), it means we can potentially use this clip. To do so, we must have already covered the interval[0, start]. The cost for that isdp[start]. - So, we can update
dp[i]withmin(dp[i], dp[start] + 1). - After checking all clips for the current
i,dp[i]will hold the minimum clips to cover[0, i]. - After the loops complete, if
dp[time]is still the infinity value, it means[0, time]cannot be covered. Return -1. - Otherwise,
dp[time]holds the minimum number of clips, so return it.
Walkthrough
We define dp[i] as the minimum number of clips needed to create a continuous video from time 0 to time i. The size of our dp array will be time + 1.
The base case is dp[0] = 0, as it takes zero clips to cover a duration of zero. All other dp[i] values are initialized to a large number (like time + 2) to signify that they are not yet reachable.
We then iterate from i = 1 to time. For each i, we try to find the best way to cover the interval [0, i]. We can do this by considering every clip [start, end]. If a clip covers the time point i (i.e., start < i <= end), it can be the last clip in our sequence. If we choose this clip, we must have already covered the interval [0, start]. The number of clips to do that is dp[start]. Therefore, the total number of clips would be dp[start] + 1. We take the minimum over all such possible clips.
The final answer is dp[time]. If dp[time] remains at its initial large value, it means the interval [0, time] is impossible to cover.
import java.util.Arrays; class Solution { public int videoStitching(int[][] clips, int time) { int[] dp = new int[time + 1]; // Initialize dp array with a value larger than any possible answer. // time + 2 is a safe choice since the max answer can be time + 1. Arrays.fill(dp, time + 2); dp[0] = 0; for (int i = 1; i <= time; i++) { for (int[] clip : clips) { int start = clip[0]; int end = clip[1]; if (start < i && i <= end) { // If this clip can cover time i, we check the cost to cover up to its start time. if (dp[start] != time + 2) { dp[i] = Math.min(dp[i], dp[start] + 1); } } } } return dp[time] == time + 2 ? -1 : dp[time]; }}Complexity
Time
O(T * N), where T is the target time and N is the number of clips. We have a nested loop structure where the outer loop runs T times and the inner loop runs N times.
Space
O(T), where T is the target time. This is for the `dp` array.
Trade-offs
Pros
The logic is relatively straightforward, following a standard dynamic programming pattern.
It correctly solves the problem by exploring all possibilities through subproblems.
Cons
It is the least efficient approach among the three due to its nested loops, leading to a quadratic time complexity in the worst case.
Solutions
Solution
class Solution {public int videoStitching(int[][] clips, int time) { int[] last = new int[time]; for (var e : clips) { int a = e[0], b = e[1]; if (a < time) { last[a] = Math.max(last[a], b); } } int ans = 0, mx = 0, pre = 0; for (int i = 0; i < time; ++i) { mx = Math.max(mx, last[i]); if (mx <= i) { return -1; } if (pre == i) { ++ans; pre = mx; } } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.