Video Stitching

MEDIUM

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] = [start_i, end_i] indicates that the ith clip started at start_i and ended at end_i.

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 <= start_i <= end_i <= 100
1 <= time <= 100

Approaches

Checkout 3 different approaches to solve Video Stitching. Click on different approaches to view the approach and algorithm in detail.

Dynamic Programming

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 dp of size time + 1 to store the minimum number of clips to cover the interval [0, i].
Initialize dp[0] to 0 and all other elements dp[i] to a value representing infinity (e.g., time + 2, which is larger than any possible valid answer).
Iterate i from 1 to time. For each i, we want to compute dp[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 is dp[start].
So, we can update dp[i] with min(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.

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 Analysis

Time Complexity: 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 Complexity: O(T), where T is the target time. This is for the `dp` array.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Video Stitching. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Video Stitching

Patterns:

Dynamic ProgrammingGreedy

Data Structures:

Array

Companies:

Anduril |Verily |