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.
The greedy approach involves sorting the clips based on their start times, and then iteratively selecting clips that extend the coverage as far as possible. Prioritize clips with earlier start times and check how far they can extend the current coverage. If you ever get stuck where no clips can extend the coverage, it's impossible to cover the entire event, otherwise, continue until the end is covered.
This C implementation uses a greedy approach. The clips are first sorted by their start time. The code iterates over the sorted clips, updating the farthest point that can be reached. If it can't extend the coverage, the function returns -1. Otherwise, it returns the number of clips used.
Time Complexity: O(n log n), due to sorting of the clips.
Space Complexity: O(1), uses a constant amount of extra space.
In the dynamic programming approach, an array dp[] is used where dp[i] indicates the minimum number of clips needed to cover up to the i-th second. Initialize this array with a large number except for dp[0] = 0, then iterate over each second and find the minimal solution by iterating over the clips that take part in that segment.
This C solution uses a dynamic programming table (dp) to store the minimum number of clips needed to cover each time unit up to the given 'time'. Each dp[t] is updated by iterating over each available clip and checking if it participates in forming the segment [clips[i][0], clips[i][1]].
Time Complexity: O(n * time), where n is the number of clips and time is the duration.
Space Complexity: O(time), additional space to store dp array.
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:
| Approach | Complexity |
|---|---|
| Greedy Algorithm | Time Complexity: O(n log n), due to sorting of the clips. |
| Dynamic Programming | Time Complexity: O(n * time), where n is the number of clips and time is the duration. |
| Greedy | — |
| 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. |
花花酱 LeetCode 1024. Video Stitching - 刷题找工作 EP248 • Hua Hua • 5,023 views views
Watch 9 more video solutions →Practice Video Stitching with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor