Video Stitching: Greedy Interval Coverage Pattern

May 26, 20265 min read

leetcodeproblemmediumarraysgreedydynamic-programming

LeetCode 1024, Video Stitching, asks you to cover a target time range [0, time] using the fewest possible video clips. Each clip covers an interval [start, end], and clips can overlap. If the full range cannot be covered, return -1.

This is an interval coverage problem in disguise. The same greedy pattern shows up in scheduling, resource allocation, and anywhere you need to cover a continuous range with the fewest segments.

clips = [[0,2],[1,5],[1,9],[4,6],[5,9],[8,10]], T = 10. The greedy algorithm picks [0,2], [1,9], and [8,10] to cover [0, 10] with 3 clips.

Why this problem matters

Interval coverage is one of the most practical greedy patterns. Think about a surveillance system with overlapping camera recordings, or a streaming service stitching together segments of a live event. You want full coverage with the fewest pieces.

The greedy approach here is clean and efficient. Once you see how it works on Video Stitching, the same idea carries over to problems like Jump Game II (where you cover index ranges instead of time ranges) and any minimum-cover problem.

What makes this pattern worth drilling is that the logic has a few moving parts. You need to sort, track coverage, and pick the best candidate in each round. Getting all three pieces right under pressure requires practice.

The key insight

Sort the clips by start time. Then, greedily pick the clip that extends your coverage the furthest. At each step, you look at all clips whose start time falls within your current coverage, and among those, you choose the one with the largest end time. This guarantees you make maximum progress with each pick.

If at any point you cannot find a clip that starts within your current coverage, there is a gap, and the answer is -1.

The solution

def videoStitching(clips, time):
    clips.sort()
    count = 0
    coverage_end = 0
    i = 0
    n = len(clips)

    while coverage_end < time:
        farthest = coverage_end

        while i < n and clips[i][0] <= coverage_end:
            farthest = max(farthest, clips[i][1])
            i += 1

        if farthest == coverage_end:
            return -1

        coverage_end = farthest
        count += 1

    return count

The outer while loop runs once per clip we pick. Inside, the inner loop scans all clips that start within the current coverage window and finds the one reaching furthest. If farthest does not advance past coverage_end, there is a gap and we return -1. Otherwise, we extend our coverage and increment the count.

The variable i never resets. Each clip is examined exactly once across all iterations of the inner loop, so the total scan is linear.

The condition clips[i][0] <= coverage_end uses "less than or equal" because a clip starting exactly where your coverage ends creates a seamless join with no gap.

Practice greedy patterns with spaced repetition

Visual walkthrough

Let's trace the greedy algorithm on clips = [[0,2],[1,5],[1,9],[4,6],[5,9],[8,10]] with time = 10. Watch how coverage grows with each pick.

Step 1: Sort clips by start time

Sort all clips by start time. Coverage begins at 0 and we need to reach T = 10.

Step 2: Pick [0,2], the only clip starting at 0

We must start with a clip at 0. Pick [0,2]. Coverage now reaches time 2. Count = 1.

Step 3: Among clips starting at or before 2, pick [1,9]

Clips [1,5] and [1,9] both start before our coverage end (2). Pick [1,9] because it extends furthest. Coverage reaches 9. Count = 2.

Step 4: Among clips starting at or before 9, pick [8,10]

Clips [4,6], [5,9], and [8,10] all start before 9. Pick [8,10] since it reaches 10. Coverage reaches T = 10. Count = 3.

Step 5: Coverage complete. Answer = 3

Three clips cover the entire range [0, 10] with no gaps. This is the minimum number needed.

Three clips are enough to cover the full range. The greedy strategy always picks the clip extending furthest, which is why [1,9] beats [1,5] in step 3. That single decision avoids needing an extra clip.

Complexity analysis

Approach	Time	Space
Greedy	O(n log n)	O(1)

Time: O(n log n) from sorting. The two-pointer scan after sorting is O(n) since each clip is visited once. The sort dominates.

Space: O(1) extra space beyond the input (assuming in-place sort). We only track a few integer variables.

The building blocks

1. Sort-first reduction

Sorting clips by start time creates a crucial invariant: as you scan left to right, you know every clip that could extend your current coverage appears in a contiguous block. Without sorting, you would need to re-scan the entire list at every step.

This is the same principle behind Merge Intervals (sort by start, then sweep) and Jump Game II (process positions in order). Whenever a brute force involves re-scanning to find the best option, sorting often converts it to a single linear pass.

clips.sort()

2. Greedy farthest-reach selection

At each round, among all candidates that overlap with your current coverage, pick the one that extends furthest. This is optimal because you are always making maximum progress. No other valid choice could produce a shorter sequence.

This same "farthest reach" logic powers Jump Game II. There, you track the farthest index reachable from the current jump window. Here, you track the farthest time reachable from clips starting within your coverage.

while i < n and clips[i][0] <= coverage_end:
    farthest = max(farthest, clips[i][1])
    i += 1

Drill greedy building blocks with spaced repetition

Edge cases

No clip starts at 0. If no clip has start == 0, the range [0, time] cannot be covered. The algorithm handles this because farthest stays at 0 and we return -1 immediately.
time is 0. The range is empty, so 0 clips are needed. The outer loop never executes and we return 0.
A single clip covers the whole range. Something like [[0, 10]] with time = 10. One iteration picks it, coverage reaches time, and we return 1.
Multiple clips with the same start. Sorting is stable, but it does not matter. The inner loop considers all of them and picks the max end, so duplicated start values are handled naturally.
A gap in coverage. If clips are [[0,3],[5,10]] with time = 10, no clip bridges the gap from 3 to 5. After picking [0,3], farthest stays at 3 and we return -1.

From understanding to recall

Video Stitching is a great drill problem because the greedy logic is compact but has real structure. You need to remember: sort first, then use two pointers to find the farthest-reaching clip in each round, and handle the gap case. Missing any of these pieces leads to a bug.

The pattern generalizes well. Once you can write this from memory, Jump Game II becomes almost the same problem with different input formatting. Interval coverage and farthest-reach selection are building blocks that keep showing up.

Spaced repetition is the fastest way to move this from "I understand it" to "I can write it cold." Revisit the problem at increasing intervals and you will lock in the sort, scan, and extend pattern permanently.

Jump Game II - Same farthest-reach greedy pattern applied to index jumps
Merge Intervals - The foundational sort-and-sweep interval technique
Insert Interval - Interval manipulation after sorting

If you want to build real fluency with greedy interval problems, reading once is not enough. Drill the pattern until the sort, scan, and extend steps come automatically.

Try CodeBricks free