Watch 10 video solutions for Video Stitching, a medium level problem involving Array, Dynamic Programming, Greedy. This walkthrough by Hua Hua has 5,023 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
[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 <= 100Problem Overview: You receive several video clips where each clip is represented as [start, end]. The goal is to stitch together the minimum number of clips so the entire interval [0, time] is covered. Clips can overlap and can be cut into smaller segments.
Approach 1: Greedy Algorithm (O(n log n) time, O(1) space)
The greedy strategy works similarly to the classic interval coverage problem. First, sort the clips by their start time. Then iterate through them while tracking the farthest point you can reach with clips that begin before or at the current coverage boundary. Each time the current segment ends, select the clip that extends coverage the farthest. This is conceptually similar to the jump expansion technique used in interval coverage problems. The key insight: whenever multiple clips overlap the current boundary, always choose the one with the maximum end value. Sorting costs O(n log n), and the single pass through the clips keeps the rest of the work linear.
This approach fits naturally under Greedy strategy because each decision locally maximizes the reachable interval. Once a segment is chosen, you never need to reconsider earlier clips.
Approach 2: Dynamic Programming (O(n * T) time, O(T) space)
The dynamic programming approach builds a table where dp[t] represents the minimum number of clips needed to cover the interval [0, t]. Initialize all values with a large number and set dp[0] = 0. For each clip [start, end], update all reachable times between start and end. The transition looks like dp[i] = min(dp[i], dp[start] + 1) for all i in that range. This effectively tries every clip as a possible extension of an already covered segment.
This method models the problem as incremental coverage and is easier to reason about if you're comfortable with Dynamic Programming. However, it performs more updates than the greedy method and becomes slower when the target time T grows.
Recommended for interviews: The greedy solution is the expected answer in most interviews because it reduces the problem to interval expansion with optimal local choices. Interviewers typically want to see you recognize the similarity to interval covering or jump-style problems on arrays. Starting with a brute-force or DP explanation shows understanding, but arriving at the greedy optimization demonstrates stronger algorithmic intuition with Array interval problems.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Interval Expansion | O(n log n) | O(1) | Best general solution. Efficient when clips must be merged to cover an interval. |
| Dynamic Programming | O(n * T) | O(T) | Useful for reasoning about incremental coverage when time range is small. |