LeetCode 1024: Video Stitching

Problem Restatement

We are given an array clips where clips[i] = [start_i, end_i] represents a video clip covering the time interval [start_i, end_i].

We want to cover the interval [0, time] by choosing some of these clips.

We need to return the minimum number of clips needed, or -1 if it is impossible.

Clips can be cut, so using only a portion of a clip is allowed.

The official constraints state that 1 <= clips.length <= 100, 0 <= start_i <= end_i <= 100, and 1 <= time <= 100.

Input and Output

Function shape:

def videoStitching(clips: list[list[int]], time: int) -> int:
    ...

Examples

Example 1:

clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]]
time = 10

Choose clips [0,2], [1,9], [8,10]:

• [0,2] covers [0,2]
• [1,9] extends coverage to [0,9]
• [8,10] extends to [0,10]

Answer:

3

Example 2:

clips = [[0,1],[1,2]]
time = 5

These two clips only cover [0,2], not [0,5].

Answer:

-1

Key Insight

This is the classic greedy interval covering problem.

At each step, from the current coverage end, greedily pick the clip that extends coverage the furthest.

Algorithm

1. Build a map max_end[s] = the furthest end reachable from start s.
2. Initialize count = 0, current_end = 0, farthest = 0.
3. For each time unit t from 0 to time - 1:
   • Update farthest = max(farthest, max_end.get(t, 0)).
   • If t == current_end:
     • If farthest == current_end, return -1 (stuck).
     • Increment count.
     • current_end = farthest.
4. Return count.

Correctness

At each step, we pick the clip that extends coverage the most. This greedy choice is optimal because choosing any clip with a shorter extension would only make future choices harder.

If at any position we cannot extend coverage, the task is impossible.

Edge Cases

• Initialize the base states explicitly; most wrong answers come from an implicit zero that should not be allowed.
• Confirm the iteration order matches the recurrence dependencies.
• For optimization DP, separate impossible states from valid states with value 0.

Complexity

Common Pitfalls

• Do not overwrite a state before all transitions that still need the old value have used it.
• Use the problem constraints to choose between full tables and compressed state.

Implementation

class Solution:
    def videoStitching(self, clips: list[list[int]], time: int) -> int:
        max_end = [0] * (time + 1)
        for s, e in clips:
            if s <= time:
                max_end[s] = max(max_end[s], e)

        count = 0
        current_end = 0
        farthest = 0

        for t in range(time):
            farthest = max(farthest, max_end[t])
            if t == current_end:
                if farthest == current_end:
                    return -1
                count += 1
                current_end = farthest

        return count

Code Explanation

Build the array of furthest reachable endpoints:

max_end = [0] * (time + 1)
for s, e in clips:
    if s <= time:
        max_end[s] = max(max_end[s], e)

Greedy scan:

for t in range(time):
    farthest = max(farthest, max_end[t])
    if t == current_end:
        if farthest == current_end:
            return -1
        count += 1
        current_end = farthest

When we reach current_end, we must pick the next clip. The best choice extends coverage to farthest.

If farthest has not advanced beyond current_end, it is impossible.

Testing

def run_tests():
    s = Solution()

    assert s.videoStitching([[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], 10) == 3
    assert s.videoStitching([[0,1],[1,2]], 5) == -1
    assert s.videoStitching([[0,5]], 5) == 1
    assert s.videoStitching([[0,1],[0,2],[0,3]], 3) == 1
    assert s.videoStitching([[0,1],[1,2],[2,3]], 3) == 3

    print("all tests passed")

run_tests()