Greedy — Video Stitching
↗ LeetCode: Video Stitching · Medium · pattern chapter →
Cover [0, T] with fewest clips [a, b]. Return -1 if impossible.
Example 1 — clips=[[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], T=10 → 3Example 2 — clips=[[0,1],[1,2]], T=5 → -1Example 3 — clips=[[0,5],[0,5],[0,5]], T=5 → 1 (any one clip covers)
Constraints — 1 ≤ n ≤ 100; 0 ≤ T ≤ 100. Brute subset enumeration is 2ⁿ — at n=25 already 3·10⁷. Greedy is O(n log n) — trivially fast.
Interview timer00:00
Approach 1 — Brute subset enumeration
Intuition. Try every subset of clips. Check if they cover [0, T] (sort by start, verify each consecutive overlap).
Complexity — Time O(2ⁿ · n log n); Space O(n). Dies past n=20. In an interview say "same shape as Jump Game II — farthest reach greedy → O(n log n)."
Approach 2 — Sort by start + farthest reach (canonical)
Insight. Same shape as Jump Game II. Sort by start. Maintain curEnd; while iterating clips with start ≤ curEnd, extend farReach. When exhausted, use one clip (advance curEnd = farReach).
int videoStitching(int[][] clips, int T) {
Arrays.sort(clips, (a, b) -> a[0] - b[0]);
int used = 0, curEnd = 0, farReach = 0, i = 0;
while (curEnd < T) {
while (i < clips.length && clips[i][0] <= curEnd)
farReach = Math.max(farReach, clips[i++][1]);
if (farReach <= curEnd) return -1;
used++; curEnd = farReach;
}
return used;
}Complexity — Time O(n log n); Space O(1). Say aloud in an interview: "farthest-reach greedy — one of the classic 3 greedy templates (also: earliest-finish, sort-by-ratio)."
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Brute subsets | O(2ⁿ · n log n) | O(n) | TLE past n=20 |
| Sort + reach | O(n log n) | O(1) | Canonical |
When to use which
- Min intervals covering [0,T] → farthest reach.
- Same-start bucket by max-end → O(T) without sort.