Video Stitching solution and explanation
Google
9 more videos on this problem
花花酱 LeetCode 1024. Video Stitching - 刷题找工作 EP248Hua Hua · 11:48 · 5K views
LeetCode 1024. Video StitchingHappy Coding · 25:07 · 4K views
LeetCode 1024 - Video StitchingLight Of Truth · 14:29 · 2K views
【每日一题】1024. Video Stitching, 07/09/2019Huifeng Guan · 24:26 · 1K views
LeetCode 1024 | Video Stitching | Greedy | JavaSleepy Cracker · 6:22 · 932 views
Разбор задачи 1024 leetcode.com Video Stitching3.5 задачи в неделю · 1:13:21 · 547 views
猩猩的乐园 Leetcode 1024 Video Stitching猩猩的乐园 · 7:23 · 513 views
Video Stitching, Medium, LeetCode 1024H William Polenz · 14:45 · 233 views
LeetCode, задача "Video stitching"Прикольное проектное программирование · 11:52 · 185 views
Video Stitching - Leetcode 1024 - C++Don’t Wanna LeetCode · 8:38 · 109 views
The problem
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
Approach overview
Problem 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 1: Greedy Algorithm
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.
def videoStitching(clips, time):
clips.sort()
end, farthest, count, i = 0, 0, 0, 0
while end < time:
while i < len(clips) and clips[i][0] <= end:
farthest = max(farthest, clips[i][1])
i += 1
if end == farthest:
return -1
end = farthest
count += 1
return countimport java.util.*;
class Solution {
public int videoStitching(int[][] clips, int time) {
Arrays.sort(clips, (a, b) -> Integer.compare(a[0], b[0]));
int end = 0, farthest = 0, count = 0, i = 0;
while (end < time) {
while (i < clips.length && clips[i][0] <= end) {
farthest = Math.max(farthest, clips[i][1]);
i++;
}
if (end == farthest) return -1;
end = farthest;
count++;
}
return count;
}
}#include <algorithm>
#include <vector>
using namespace std;
int videoStitching(vector<vector<int>>& clips, int time) {
sort(clips.begin(), clips.end());
int end = 0, farthest = 0, count = 0, i = 0;
while (end < time) {
while (i < clips.size() && clips[i][0] <= end) {
farthest = max(farthest, clips[i][1]);
i++;
}
if (end == farthest) return -1;
end = farthest;
count++;
}
return count;
}function videoStitching(clips, time) {
clips.sort((a, b) => a[0] - b[0]);
let end = 0, farthest = 0, count = 0, i = 0;
while (end < time) {
while (i < clips.length && clips[i][0] <= end) {
farthest = Math.max(farthest, clips[i][1]);
i++;
}
if (end === farthest) return -1;
end = farthest;
count++;
}
return count;
}#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
int *clipA = *(int**)a;
int *clipB = *(int**)b;
return clipA[0] - clipB[0];
}
int videoStitching(int** clips, int clipsSize, int* clipsColSize, int time) {
qsort(clips, clipsSize, sizeof(int*), compare);
int end = 0, farthest = 0, count = 0, i = 0;
while (end < time) {
while (i < clipsSize && clips[i][0] <= end) {
if (clips[i][1] > farthest) {
farthest = clips[i][1];
}
i++;
}
if (end == farthest) {
return -1;
}
end = farthest;
count++;
}
return count;
}using System;
public class Solution {
public int VideoStitching(int[][] clips, int time) {
Array.Sort(clips, (a, b) => a[0].CompareTo(b[0]));
int end = 0, farthest = 0, count = 0, i = 0;
while (end < time) {
while (i < clips.Length && clips[i][0] <= end) {
farthest = Math.Max(farthest, clips[i][1]);
i++;
}
if (end == farthest) return -1;
end = farthest;
count++;
}
return count;
}
}This Python solution sorts the input by start time and selects the clip extending coverage the farthest. It returns the count of clips required or -1 if coverage cannot reach the target.
Time Complexity: O(n log n), from sorting the clips.
Space Complexity: O(1), since no additional space proportional to input size is used.
Approach 2: Dynamic Programming
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.
def videoStitching(clips, time):
dp = [float('inf')] * (time + 1)
dp[0] = 0
for t in range(1, time + 1):
for clip in clips:
if clip[0] < t <= clip[1]:
dp[t] = min(dp[t], dp[clip[0]] + 1)
return -1 if dp[time] == float('inf') else dp[time]import java.util.*;
class Solution {
public int videoStitching(int[][] clips, int time) {
int[] dp = new int[time + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
for (int t = 1; t <= time; t++) {
for (int[] clip : clips) {
if (clip[0] < t && t <= clip[1]) {
dp[t] = Math.min(dp[t], dp[clip[0]] + 1);
}
}
}
return dp[time] == Integer.MAX_VALUE ? -1 : dp[time];
}
}#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
int videoStitching(vector<vector<int>>& clips, int time) {
vector<int> dp(time + 1, INT_MAX);
dp[0] = 0;
for (int t = 1; t <= time; ++t) {
for (auto& clip : clips) {
if (clip[0] < t && t <= clip[1]) {
dp[t] = min(dp[t], dp[clip[0]] + 1);
}
}
}
return dp[time] == INT_MAX ? -1 : dp[time];
}function videoStitching(clips, time) {
let dp = new Array(time + 1).fill(Infinity);
dp[0] = 0;
for (let t = 1; t <= time; ++t) {
for (let [start, end] of clips) {
if (start < t && t <= end) {
dp[t] = Math.min(dp[t], dp[start] + 1);
}
}
}
return dp[time] === Infinity ? -1 : dp[time];
}#include <limits.h>
int videoStitching(int** clips, int clipsSize, int* clipsColSize, int time) {
int dp[101];
for (int i = 0; i <= time; i++) dp[i] = INT_MAX;
dp[0] = 0;
for (int t = 1; t <= time; t++) {
for (int i = 0; i < clipsSize; i++) {
if (clips[i][0] < t && t <= clips[i][1]) {
if (dp[clips[i][0]] != INT_MAX) {
dp[t] = dp[t] < dp[clips[i][0]] + 1 ? dp[t] : dp[clips[i][0]] + 1;
}
}
}
}
return dp[time] == INT_MAX ? -1 : dp[time];
}using System;
public class Solution {
public int VideoStitching(int[][] clips, int time) {
int[] dp = new int[time + 1];
Array.Fill(dp, int.MaxValue);
dp[0] = 0;
for (int t = 1; t <= time; t++) {
foreach (int[] clip in clips) {
if (clip[0] < t && t <= clip[1]) {
dp[t] = Math.Min(dp[t], dp[clip[0]] + 1);
}
}
}
return dp[time] == int.MaxValue ? -1 : dp[time];
}
}Python's dynamic approach uses a list, dp, initialized to infinity, ensuring the minimum clip counts to cover up to each very second. The list is updated by iterating through all clips and calculating minimal combinations.
Time Complexity: O(n * time), where n is the number of clips.
Space Complexity: O(time), storing number of clips needed for each second up to the total time.
Approach 3: 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:
func videoStitching(clips [][]int, time int) int {
last := make([]int, time)
for _, v := range clips {
a, b := v[0], v[1]
if a < time {
last[a] = max(last[a], b)
}
}
ans, mx, pre := 0, 0, 0
for i, v := range last {
mx = max(mx, v)
if mx <= i {
return -1
}
if pre == i {
ans++
pre = mx
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Algorithm | Time Complexity: O(n log n), from sorting the clips. |
| Dynamic Programming | Time Complexity: O(n * time), where n is the number of clips. |
| Greedy | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Video Stitching easy or hard?
Video Stitching is considered a medium difficulty problem. The challenge lies in recognizing that it reduces to an interval coverage greedy strategy rather than trying every combination of clips. Once the interval expansion idea is clear, the implementation becomes straightforward.
How to solve Video Stitching in O(n)?
A near O(n) greedy scan is possible if clips are preprocessed or stored by start time similar to the Jump Game approach. Build an array that tracks the farthest reachable end for each start point, then expand coverage step by step. This avoids sorting and keeps the traversal linear with respect to the target time.
What is the best approach for Video Stitching?
The greedy interval expansion approach is the most efficient solution. Sort clips by start time and always choose the clip that extends the current coverage the farthest. This guarantees the minimum number of clips while running in O(n log n) time due to sorting and O(1) extra space.
What data structure is used in Video Stitching?
The problem primarily uses arrays and interval processing. The greedy solution relies on sorting and sequential scanning of intervals, while the dynamic programming solution maintains a DP array that tracks the minimum clips needed to cover each time point.
What is the time complexity of Video Stitching?
The optimal greedy solution runs in O(n log n) time because the clips must first be sorted by start time. After sorting, a single linear pass determines the minimum clips required. Space complexity remains O(1) since only a few variables track the current and farthest coverage.
Video Stitching Python or Java solution approach?
Both Python and Java implementations typically follow the same greedy pattern: sort clips by start time, iterate through overlapping clips, and update the farthest reachable endpoint. The algorithmic complexity remains O(n log n) with constant extra space regardless of language.
Is Video Stitching asked at Google, Amazon, or Meta?
Video Stitching is a common interval coverage problem frequently appearing in interviews at large tech companies. Variants of interval merging and greedy coverage are known to appear at companies like Google, Amazon, and Meta because they test greedy reasoning and array processing.