LeetCode 1024 - Video Stitching

The problem asks us to cover a sporting event that lasts time seconds using a set of video clips. Each clip is defined by its start and end times, [starti, endi], and clips can overlap or extend beyond each other.

leetcodemediumarraydynamic-programminggreedy

LeetCode Problem 1024

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Greedy

Solution

Problem Understanding

The problem asks us to cover a sporting event that lasts time seconds using a set of video clips. Each clip is defined by its start and end times, [starti, endi], and clips can overlap or extend beyond each other. We can cut clips into smaller segments freely, meaning that if a clip covers [0,7], we can use [0,1], [1,3], [3,7], or any subdivision to fill gaps.

The goal is to determine the minimum number of clips needed to cover the full interval [0, time]. If it is impossible to cover the entire interval, we should return -1.

The input constraints are manageable (clips.length <= 100, time <= 100), which allows us to consider solutions that are O(n²) or O(n*maxTime) without performance issues. Important edge cases include clips that do not start at 0, gaps between clips, overlapping clips, and clips that completely cover or extend beyond the required interval.

The problem guarantees that each clip has 0 <= starti <= endi <= 100 and time <= 100, so we do not have negative times or excessively large inputs, simplifying the handling of ranges.

Approaches

Brute Force

A naive brute-force approach would attempt to try every combination of clips to cover [0, time]. We could recursively select clips starting from 0, track the segments they cover, and try every possible sequence to cover the interval. This guarantees correctness because we explore all combinations, but the time complexity is exponential (O(2^n)), making it impractical for n = 100.

Optimal Approach

The key insight is to recognize that this is analogous to the jump game problem. We want to iteratively pick clips that extend coverage the farthest. If we sort clips by start time, we can greedily select clips that start before or at the current coverage and extend the end as far as possible. Each selection represents adding a clip to the solution.

This greedy approach works because at each step we always maximize the coverage, which minimizes the number of clips. No dynamic programming is necessary because the greedy selection guarantees minimal clip count.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Try all combinations recursively to cover [0, time]
Greedy / Optimal O(n + time) O(time) Use an array maxEnd to track the farthest reach from each start, iterate linearly to count clips

Algorithm Walkthrough

  1. Create an array maxEnd of size time + 1 initialized to 0. This will store, for each second t, the farthest end that can be reached by any clip starting at or before t.
  2. Iterate through each clip [start, end] and update maxEnd[start] = max(maxEnd[start], end). This ensures that from a given start time, we know how far we can extend.
  3. Initialize three variables: clipsUsed = 0, currentEnd = 0, and nextEnd = 0. currentEnd represents the end of coverage with the current number of clips, nextEnd is the farthest reachable point with the next clip.
  4. Iterate i from 0 to time - 1. For each second i:

  • Update nextEnd = max(nextEnd, maxEnd[i]).

  • If i reaches currentEnd, it means we need to add a new clip to continue coverage:

  • Increment clipsUsed.

  • Set currentEnd = nextEnd.

  • If i exceeds nextEnd at any point, return -1 because coverage is impossible.

  1. After the iteration, clipsUsed contains the minimum number of clips needed.

Why it works

At each step, we choose the clip (or combination of overlapping clips) that extends our coverage the farthest. This greedy choice guarantees that no solution can use fewer clips to reach the same coverage. If at any point the next extension is not possible, it is impossible to cover the event.

Python Solution

from typing import List

class Solution:
    def videoStitching(self, clips: List[List[int]], time: int) -> int:
        maxEnd = [0] * (time + 1)
        for start, end in clips:
            if start <= time:
                maxEnd[start] = max(maxEnd[start], min(end, time))
        
        clipsUsed = 0
        currentEnd = 0
        nextEnd = 0
        
        for i in range(time):
            nextEnd = max(nextEnd, maxEnd[i])
            if i == currentEnd:
                if nextEnd == currentEnd:
                    return -1
                clipsUsed += 1
                currentEnd = nextEnd
        
        return clipsUsed

Explanation

We first preprocess clips into maxEnd to know the farthest reach from each start. The loop iterates through each second of the target interval. If we reach the end of the current coverage, we add a clip to extend coverage to nextEnd. If at any moment we cannot extend further (nextEnd == currentEnd), we return -1.

Go Solution

func videoStitching(clips [][]int, time int) int {
    maxEnd := make([]int, time+1)
    for _, clip := range clips {
        start, end := clip[0], clip[1]
        if start <= time {
            if end > time {
                end = time
            }
            if end > maxEnd[start] {
                maxEnd[start] = end
            }
        }
    }

    clipsUsed := 0
    currentEnd := 0
    nextEnd := 0

    for i := 0; i < time; i++ {
        if maxEnd[i] > nextEnd {
            nextEnd = maxEnd[i]
        }
        if i == currentEnd {
            if nextEnd == currentEnd {
                return -1
            }
            clipsUsed++
            currentEnd = nextEnd
        }
    }

    return clipsUsed
}

Explanation

The Go implementation mirrors the Python logic. We use a slice for maxEnd. Updating nextEnd and counting clipsUsed works identically. Go requires explicit handling of slice indexing, but no additional complexities arise.

Worked Examples

Example 1

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

  • maxEnd after preprocessing: [0]=2, [1]=9, [4]=6, [5]=9, [8]=10
  • Iteration steps:
i currentEnd nextEnd Action
0 0 2 i == currentEnd -> clipsUsed=1, currentEnd=2
1 2 9 continue
2 2 9 i == currentEnd -> clipsUsed=2, currentEnd=9
3..8 9 10 continue
9 9 10 i == currentEnd -> clipsUsed=3, currentEnd=10

Result: 3

Example 2

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

  • maxEnd after preprocessing: [0]=1, [1]=2
  • Iteration: i reaches 2, nextEnd = 2. At i=2, i == currentEnd, nextEnd == currentEnd -> return -1

Example 3

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

  • maxEnd after preprocessing: [0]=4, [1]=4, [2]=6, [3]=4, [4]=7, [5]=7, [6]=9
  • Iteration:
i currentEnd nextEnd Action
0 0 4 i == currentEnd -> clipsUsed=1, currentEnd=4
1..3 4 7 continue
4 4 7 i == currentEnd -> clipsUsed=2, currentEnd=7
5..6 7 9 continue
7 7 9 i == currentEnd -> clipsUsed=3, currentEnd=9

Result: 3

Complexity Analysis

Measure Complexity Explanation
Time O(n + time) O(n) to preprocess clips into maxEnd, O(time) to iterate over coverage
Space O(time) The maxEnd array requires time + 1 space

Given time and n ≤ 100, this solution is very efficient.

Test Cases

# Provided examples
assert Solution().videoStitching([[0,2],[4,