Video Stitching

Share

Find minimum number of clips to cover video [0, T] exactly.

Example 1
Input: clips=[[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], T=10 → Output: 3
Example 2
Input: clips=[[0,1],[1,2]], T=5 → Output: -1

Solution Approach

Greedy jump game approach: from each position, find clip extending farthest.

  • Sort clips by start time
  • Greedy: track curEnd and farthest from current position
  • For each position: find clip starting at or before curEnd extending farthest
  • Advance curEnd to farthest, increment count
  • If cant extend, return -1
Java
public int videoStitching(int[][] clips, int time) {
    int[] maxEnd = new int[time + 1];
    for (int[] c : clips) if (c[0] <= time) maxEnd[c[0]] = Math.max(maxEnd[c[0]], c[1]);
    int count = 0, curEnd = 0, farthest = 0;
    for (int i = 0; i <= time; i++) {
        if (i > farthest) return -1;
        farthest = Math.max(farthest, maxEnd[i]);
        if (i == curEnd && i < time) { count++; curEnd = farthest; }
    }
    return count;
}
  • Time Complexity: O(n+T)
  • Space Complexity: O(T)