# Video Stitching
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/video-stitching)
Canonical: https://scaleengineer.com/dsa/problems/video-stitching
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
**Companies:** [Anduril](https://scaleengineer.com/companies/anduril), [Verily](https://scaleengineer.com/companies/verily)
---
## 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 <= 100`
* `0 <= starti <= endi <= 100`
* `1 <= time <= 100`

# Approaches
## 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.
**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.
**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.
### Explanation
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.

```java
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];
    }
}
```
### 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.

## Greedy Approach with Sorting
This problem has an optimal substructure and greedy choice property, making it suitable for a greedy algorithm. The idea is to always make the locally optimal choice of extending the current covered range as far as possible. At any point, if we have covered the interval `[0, current_end]`, we select the next clip that starts at or before `current_end` and has the maximum end time. This ensures we cover the maximum new ground with each clip we add.
**Time:** O(N log N), where N is the number of clips. The sorting step dominates the complexity. The subsequent greedy pass is O(N) because we iterate through the clips with a single pointer `i`. · **Space:** O(log N) or O(N), depending on the space used by the sorting algorithm.
**Pros:** More efficient than the dynamic programming approach.; The logic is intuitive and mirrors other greedy interval-based problems like Jump Game II.
**Cons:** The sorting step adds an `O(N log N)` time complexity, which can be slower than a linear-time approach for certain distributions of N and T.
### Explanation
We start by sorting the clips by their start times. This helps in efficiently finding the next clip to extend our coverage.

We maintain a variable `current_end` representing the farthest point in time we have covered, initialized to 0. We also have a `count` for the number of clips used. The process is iterative: in each step, we select one clip.

While our `current_end` is less than `time`, we look for the best next clip. We iterate through the sorted clips that start at or before our `current_end`. Among all such clips, we find the one that reaches the farthest (has the maximum end time). Let's call this maximum reach `next_end`.

If, after checking all relevant clips, `next_end` is no better than `current_end`, it means we're stuck in a gap and cannot proceed. In this case, it's impossible to cover the entire `[0, time]` interval, so we return -1.

Otherwise, we have successfully extended our coverage. We increment our `count` by one (for the clip we just chose) and update `current_end` to `next_end`. We repeat this process until `current_end` reaches or exceeds `time`.

```java
import java.util.Arrays;

class Solution {
    public int videoStitching(int[][] clips, int time) {
        // Sort clips by start time, then by end time in descending order for a slight optimization.
        Arrays.sort(clips, (a, b) -> {
            if (a[0] != b[0]) {
                return a[0] - b[0];
            } else {
                return b[1] - a[1];
            }
        });

        int count = 0;
        int current_end = 0;
        int i = 0;
        int n = clips.length;

        while (current_end < time) {
            int next_end = current_end;
            // Find the clip that starts at or before current_end and extends the furthest.
            while (i < n && clips[i][0] <= current_end) {
                next_end = Math.max(next_end, clips[i][1]);
                i++;
            }

            // If we couldn't extend our reach, it's impossible.
            if (next_end == current_end) {
                return -1;
            }

            // We've chosen one more clip.
            count++;
            current_end = next_end;
        }

        return count;
    }
}
```
### Algorithm
*   First, sort the `clips` array based on their start times. This allows us to process clips in an orderly fashion.
*   Initialize `count = 0` (number of clips used), `current_end = 0` (the farthest point covered so far), and `i = 0` (an index to traverse the sorted clips).
*   Enter a loop that continues as long as `current_end < time`.
*   Inside the loop, we are trying to make one greedy choice. We first find the maximum possible reach (`next_end`) from the current position.
*   To do this, we scan through all clips that can extend our current coverage, i.e., all clips `clips[j]` where `clips[j][0] <= current_end`. We use the index `i` to avoid re-scanning clips.
*   We update `next_end` to be the maximum end time among these candidate clips.
*   After scanning all eligible clips, if `next_end` has not increased (i.e., `next_end == current_end`), it means we are stuck and cannot cover the full duration. Return -1.
*   If we can extend our coverage, we increment `count` and update `current_end = next_end`.
*   The loop continues until `current_end` covers `time`.
*   Finally, return `count`.

## Optimized Greedy Approach (Linear Time)
This is the most efficient approach, which refines the greedy strategy to achieve a linear time complexity. Instead of sorting, we pre-process the clips to determine the maximum reach from each possible start time. This allows us to solve the problem in a single pass over the time duration, similar to the optimized solution for the "Jump Game II" problem.
**Time:** O(N + T), where N is the number of clips and T is the target time. It takes O(N) to pre-process the clips and O(T) for the main loop. · **Space:** O(T), where T is the target time, for the `max_reach` array.
**Pros:** Achieves the best possible time complexity for this problem.; Avoids the `O(N log N)` overhead of sorting.
**Cons:** Requires extra space proportional to `time`, which might be a concern if `time` is very large (though not an issue with the given constraints).
### Explanation
The core idea is to transform the input clips into a more accessible format. We create an array, `max_reach`, of size `time + 1`. We populate this array by iterating through the `clips`: for each clip `[start, end]`, we set `max_reach[start] = max(max_reach[start], end)`. After this `O(N)` pre-processing step, `max_reach[i]` tells us the farthest we can get if we start a clip at time `i`.

With this `max_reach` array, we can find the solution in a single pass from `i = 0` to `time`. We maintain two pointers: `current_end`, the farthest we can reach with the clips selected so far, and `next_end`, the farthest we can reach by adding one more clip. Both are initialized to 0.

We loop from `i = 0` to `time - 1`. In each step `i`, we update `next_end = max(next_end, max_reach[i])`. This means we are checking all possible new clips that start within our current reach and finding the one that goes the farthest.

When our loop variable `i` reaches `current_end`, it means we've reached the limit of our current clip's coverage. We must take a "jump" by selecting the best clip we've found so far. We increment our clip `count` and set `current_end` to the `next_end`. If `current_end` hasn't improved, we're stuck and return -1. If the new `current_end` covers `time`, we're done and can return the `count`.

```java
class Solution {
    public int videoStitching(int[][] clips, int time) {
        if (time == 0) {
            return 0;
        }
        // max_reach[i] stores the maximum end time of a clip starting at i.
        int[] max_reach = new int[time + 1];
        for (int[] clip : clips) {
            if (clip[0] <= time) {
                max_reach[clip[0]] = Math.max(max_reach[clip[0]], clip[1]);
            }
        }

        int count = 0;
        int current_end = 0;
        int next_end = 0;

        for (int i = 0; i < time; i++) {
            // Update the farthest reach possible from the current position.
            next_end = Math.max(next_end, max_reach[i]);

            // If we are at the end of the current clip's coverage.
            if (i == current_end) {
                // If we can't move forward, it's impossible.
                if (i == next_end) {
                    return -1;
                }
                // Take the jump.
                count++;
                current_end = next_end;
                // If the new reach covers the target time, we are done.
                if (current_end >= time) {
                    return count;
                }
            }
        }

        return -1; // Should be covered by the check inside the loop.
    }
}
```
### Algorithm
*   Create an array `max_reach` of size `time + 1`. `max_reach[s]` will store the maximum end time of any clip starting at time `s`.
*   Iterate through all `clips [start, end]`. For each clip, if `start <= time`, update `max_reach[start] = max(max_reach[start], end)`. This pre-processing step takes `O(N)` time.
*   Initialize `count = 0`, `current_end = 0` (farthest reach with `count` clips), and `next_end = 0` (farthest reach with `count + 1` clips).
*   Iterate with a variable `i` from 0 up to `time - 1`.
*   In each iteration, update `next_end` with the maximum possible reach from time `i`: `next_end = max(next_end, max_reach[i])`.
*   If the iterator `i` reaches the boundary of our current coverage (`i == current_end`), it signifies that we must use a new clip to go further. This is a "jump".
*   When we jump (at `i == current_end`), we increment `count` and update `current_end` to the new `next_end` we've calculated.
*   If at the point of a jump, `current_end` has not advanced (`i == next_end`), it means we are stuck and cannot reach `time`. Return -1.
*   If at any point `current_end` becomes greater than or equal to `time`, we have successfully covered the interval, and we can return the current `count`.
*   If the loop finishes and we still haven't covered `time`, it's impossible. Return -1.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int videoStitching(vector<vector<int>> &clips, int time) {
    vector<int> last(time);
    for (auto &v : clips) {
      int a = v[0], b = v[1];
      if (a < time) {
        last[a] = max(last[a], b);
      }
    }
    int mx = 0, ans = 0;
    int pre = 0;
    for (int i = 0; i < time; ++i) {
      mx = max(mx, last[i]);
      if (mx <= i) {
        return -1;
      }
      if (pre == i) {
        ++ans;
        pre = mx;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def videoStitching(self, clips: List[List[int]], time: int) -> int: last = [0] * time for a, b in clips: if a < time: last[a] = max(last[a], b) ans = mx = pre = 0 for i, v in enumerate(last): mx = max(mx, v) if mx <= i: return - 1 if pre == i: ans += 1 pre = mx return ans

```