Video Stitching

Medium
846.

Video Stitching

Video Stitching is a medium coding problem on arrays, dynamic programming and greedy, asked in Amazon, Google and Hotstar interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} clips
 * @param {number} time
 * @return {number}
 */
var videoStitching = function(clips, time) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Video Stitching — Solution in Python, Java & C++

Video Stitching solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Video Stitching is a medium coding problem on arrays, dynamic programming and greedy, asked in Amazon, Google and Hotstar interviews.

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

Hints for Video Stitching

  1. Hint 1

    For each possible start second, only the clip reaching furthest right matters.

  2. Hint 2

    This is the jump-game shape: from everything covered so far, jump to the furthest reachable point.

  3. Hint 3

    If the furthest reach never gets past the current boundary, the coverage is impossible.

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

  1. Build maxReach over the starts below time.
  2. Sweep i from 0 to time - 1, keeping nxt, the furthest end reachable from any start seen so far.
  3. 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

Java

public static int videoStitching(int[][] clips, int time) {
    int[] maxReach = new int[time];
    for (int[] c : clips) {
        if (c[0] < time) maxReach[c[0]] = Math.max(maxReach[c[0]], c[1]);
    }
    int res = 0, curEnd = 0, nxt = 0;
    for (int i = 0; i < time; i++) {
        nxt = Math.max(nxt, maxReach[i]);
        if (i == curEnd) {
            if (nxt <= i) return -1;
            res++;
            curEnd = nxt;
        }
    }
    return res;
}

C++

int videoStitching(vector<vector<int>>& clips, int time) {
    vector<int> maxReach(time, 0);
    for (auto& c : clips) {
        if (c[0] < time) maxReach[c[0]] = max(maxReach[c[0]], c[1]);
    }
    int res = 0, curEnd = 0, nxt = 0;
    for (int i = 0; i < time; i++) {
        nxt = max(nxt, maxReach[i]);
        if (i == curEnd) {
            if (nxt <= i) return -1;
            res++;
            curEnd = 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming