Find minimum number of clips to cover video [0, T] exactly.
Input: clips=[[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], T=10 → Output: 3
Input: clips=[[0,1],[1,2]], T=5 → Output: -1
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
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)