Video Stitching

medium intervals greedy

Problem

You are given clips, each clips[i] = [start, end]. Return the minimum number of clips needed to cover the interval [0, time]. If impossible, return -1.

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

Output3

Pick [0,2], [1,9], [5,9] — three clips cover [0, 10].

clips (semicolon-separated pairs)

time

def video_stitching(clips, time):
    clips.sort()
    n, i, count = len(clips), 0, 0
    cur_end, far = 0, 0
    while cur_end < time:
        while i < n and clips[i][0] <= cur_end:
            far = max(far, clips[i][1])
            i += 1
        if far == cur_end:
            return -1
        cur_end = far
        count += 1
    return count

function videoStitching(clips, time) {
  clips.sort((a, b) => a[0] - b[0]);
  let i = 0, count = 0, curEnd = 0, far = 0;
  while (curEnd < time) {
    while (i < clips.length && clips[i][0] <= curEnd) {
      far = Math.max(far, clips[i][1]);
      i++;
    }
    if (far === curEnd) return -1;
    curEnd = far;
    count++;
  }
  return count;
}

class Solution {
    public int videoStitching(int[][] clips, int time) {
        Arrays.sort(clips, (a, b) -> a[0] - b[0]);
        int i = 0, count = 0, curEnd = 0, far = 0;
        while (curEnd < time) {
            while (i < clips.length && clips[i][0] <= curEnd) {
                far = Math.max(far, clips[i][1]);
                i++;
            }
            if (far == curEnd) return -1;
            curEnd = far;
            count++;
        }
        return count;
    }
}

int videoStitching(vector<vector<int>>& clips, int time) {
    sort(clips.begin(), clips.end());
    int i = 0, count = 0, curEnd = 0, far = 0;
    while (curEnd < time) {
        while (i < (int)clips.size() && clips[i][0] <= curEnd) {
            far = max(far, clips[i][1]);
            i++;
        }
        if (far == curEnd) return -1;
        curEnd = far;
        count++;
    }
    return count;
}

Explanation

We want to cover the whole stretch [0, time] using the fewest clips. This is a classic greedy jump game: at each step we reach as far to the right as possible, then count that as one clip used.

After sorting clips by start time, we track cur_end (the rightmost point already covered) and far (the farthest point we could reach by choosing a clip that starts within the covered area). We scan every clip whose start is ≤ cur_end and keep the maximum end in far.

Once we have looked at all reachable clips, we "use" the best one by setting cur_end = far and adding one to count. If far never moved past cur_end, there is a gap no clip can bridge, so we return -1.

Example: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10. From 0 the farthest reach is [0,2] so curEnd=2. From within 2, [1,9] reaches 9, so curEnd=9. From within 9, [5,9] ... actually [8,10] reaches 10. Three clips cover everything, so the answer is 3.

Sorting costs O(n log n); each clip is scanned once, and we only ever extend reach rightward, which guarantees the minimum number of clips.

Time: O(n log n) Space: O(1)