Video Stitching
Medium · Intervals · Array · Dynamic Programming · Greedy
Problem
A sporting event lasting time seconds was recorded as overlapping video clips. Clip i is clips[i] = [start_i, end_i], covering that span of the event. Clips may be cut into smaller segments freely.
Return the minimum number of clips needed to cover the whole event [0, time], or -1 if it cannot be covered.
Examples
Input: clips = [[0,3],[2,6],[1,4],[5,9],[6,8]], time = 9 Output: 3
[0,3], [2,6] and [5,9] together cover 0 to 9; no two clips can.
Input: clips = [[0,2],[3,5]], time = 5 Output: -1
Nothing covers the stretch between seconds 2 and 3.
Input: clips = [[0,10]], time = 4 Output: 1
The single clip already covers the whole event; the rest is cut off.
Constraints
- 1 <= len(clips) <= 100
- 0 <= start_i <= end_i <= 100
- 1 <= time <= 100
Approaches
- DP over prefix lengths — time O(n · T), space O(T)
Follow-up
This is the jump game in disguise: from second s a clip lets you "jump" to its end. The greedy works because all clips cost the same; give them prices and it fails, which is the first use case. The second asks how far the clips can reach with no finish line.
Related problems
Start free on Cariara · Coding problems · System design studio
