Video Stitching

LeetCode 1081 | Difficulty: Medium

Medium

Problem 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`

Topics: Array, Dynamic Programming, Greedy

---

Approach

Dynamic Programming

Break the problem into overlapping subproblems. Define a state (what information do you need?), a recurrence (how does state[i] depend on smaller states?), and a base case. Consider both top-down (memoization) and bottom-up (tabulation) approaches.

When to use

Optimal substructure + overlapping subproblems (counting ways, min/max cost, feasibility).

Greedy

At each step, make the locally optimal choice. The challenge is proving the greedy choice leads to a global optimum. Look for: can I sort by some criterion? Does choosing the best option now ever hurt future choices?

When to use

Interval scheduling, activity selection, minimum coins (certain denominations), Huffman coding.

---

Solutions

Solution 1: C# (Best: 203 ms)

Metric	Value
Runtime	203 ms
Memory	35.8 MB
Date	2022-01-15

Solution

public class Solution {
    public int VideoStitching(int[][] clips, int time) {
        Array.Sort(clips, (x,y) => x[0].CompareTo(y[0]));
    int i=0, maxReach = 0, count=0;
    while(maxReach < time)
    {
        int currentReach = 0;
        while(i<clips.Length && clips[i][0]<=maxReach)
        {
            currentReach = Math.Max(currentReach, clips[i][1]);
            i++;
        }
        if(currentReach <= maxReach) return -1;
        maxReach = currentReach;
        count++;
    }
    
    return count;
    }
}

---

Complexity Analysis

Approach	Time	Space
DP (2D)	$O(n × m)$	$O(n × m)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Define the DP state clearly. Ask: "What is the minimum information I need to make a decision at each step?"
• Consider if you can reduce space by only keeping the last row/few values.
• LeetCode provides 2 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: What if we sort the intervals? Considering the sorted intervals, how can we solve the problem with dynamic programming?

Hint 2: Let's consider a DP(pos, limit) where pos represents the position of the current interval we are gonna take the decision and limit is the current covered area from [0 - limit]. This DP returns the minimum number of taken intervals or infinite if it's not possible to cover the [0 - T] section.