Video Stitching — Medium Problem & Solution

clips[i] = [starti, endi] is a clip of a sporting event that covers that interval of seconds. Clips may be cut to any sub-interval.

Difficulty: Medium
Topics: Arrays, Dynamic Programming, Greedy, Intervals
Asked at: Amazon, Google, Hotstar
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

clips[i] = [start_i, end_i] is a clip of a sporting event that covers that interval of seconds. Clips may be cut to any sub-interval.

Return the minimum number of clips needed to cover the whole event [0, time], or -1 if it cannot be covered.

Example 1

Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10
Output: 3
Explanation: Take [0,2], [1,9] and [8,10].

Example 2

Input: clips = [[0,1],[1,2]], time = 5
Output: -1
Explanation: Nothing covers past second 2.

Example 3

Input: clips = [[0,4],[2,8]], time = 5
Output: 2

Constraints

1 <= clips.length <= 100
0 <= start_i <= end_i <= 100
1 <= time <= 100

How to solve Video Stitching

Reduce the clips to maxReach[s], the furthest end among clips starting at s, then run the interval-covering greedy: repeatedly extend to the furthest point reachable from anywhere already covered.

Approach

Build maxReach over the starts below time.
Sweep i from 0 to time - 1, keeping nxt, the furthest end reachable from any start seen so far.
When i reaches the current boundary curEnd, commit a clip: if nxt <= i the event cannot be covered, otherwise increment the count and move the boundary to nxt.

Why it works

Only the furthest-reaching clip per start can ever be optimal — any other clip with the same start is contained in it. Committing to the furthest reach at each boundary is the standard interval-covering greedy: delaying the choice cannot extend coverage further, and taking a shorter clip only forces at least as many clips later.

Complexity

Time — O(n + time)
Space — O(time)

Pitfalls

A clip starting at or after time is useless and must not index past the array.
The failure test is nxt <= i at a boundary — a gap means no clip bridges it.
Coverage must reach time itself, which is why the sweep runs over [0, time - 1] seconds of interval.

Reference solution

Python

from typing import List

def videoStitching(clips: List[List[int]], time: int) -> int:
    max_reach = [0] * time
    for s, e in clips:
        if s < time:
            max_reach[s] = max(max_reach[s], e)
    res = cur_end = nxt = 0
    for i in range(time):
        nxt = max(nxt, max_reach[i])
        if i == cur_end:
            if nxt <= i:
                return -1
            res += 1
            cur_end = nxt
    return res

JavaScript

var videoStitching = function(clips, time) {
    var maxReach = [];
    for (var t = 0; t < time; t++) maxReach.push(0);
    for (var i = 0; i < clips.length; i++) {
        var s = clips[i][0], e = clips[i][1];
        if (s < time && e > maxReach[s]) maxReach[s] = e;
    }
    var res = 0, curEnd = 0, nxt = 0;
    for (var j = 0; j < time; j++) {
        if (maxReach[j] > nxt) nxt = maxReach[j];
        if (j === curEnd) {
            if (nxt <= j) return -1;
            res++;
            curEnd = nxt;
        }
    }
    return res;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue