Video Stitching
Medium · intervals
A live event lasts total seconds, from second 0 to second total. It was filmed by several cameras, each of which kept a clip: clips[i] = [start, end] is a recording of the stretch from second start to second end. Clips may overlap, and a clip may run past the end of the event.
Pick as few clips as you can so that together they cover every moment from 0 to total with no gap. Two clips that meet at exactly one second, such as [0, 4] and [4, 9], leave no gap.
Return the smallest number of clips needed, or -1 if the whole event cannot be covered.
Examples
Example 1
Input: clips = [[0, 3], [2, 6], [5, 9]], total = 8
Output: 3
Seconds 0 to 3, 2 to 6 and 5 to 9 together cover 0 to 8, and no two of them are enough.
Example 2
Input: clips = [[0, 4], [3, 10], [1, 2]], total = 9
Output: 2
[0, 4] and [3, 10] overlap and together cover everything from 0 to 10.
Example 3
Input: clips = [[0, 2], [3, 6]], total = 6
Output: -1
Nothing records the stretch between second 2 and second 3.
Constraints
- 1 <= len(clips) <= 1000
- clips[i] has exactly two numbers, start and end
- 0 <= start < end <= 1000
- 1 <= total <= 1000