Dynamic Programming - Video Stitching

Given a list of clips with [start, end] that are within range [0, time], find the minimum number of clips to cover the entire range [0, time]. Return -1 if impossible.

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

Input: clips=[[0,1],[1,2]], time=5 → Output: -1

Greedy: sort by start. At each step greedily pick the clip that starts at or before current reach and extends furthest.

Sort clips by start.
Track current reach and the farthest we can extend in the next round.
When we pass a "checkpoint" (need a new clip): update reach to farthest, increment count.
If no clip starts at or before current reach, return -1.

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

Time Complexity: O(N log N)
Space Complexity: O(1)