hardGreedyPure DSA~30 min
Fewest Clips to Cover a Time Window
You assemble a recording covering [0, time] from overlapping clips, each spanning a sub-interval. Clips can be cut and overlapped freely. Find the minimum number of clips that fully cover the window.
Problem
Given an array clips where clips[i] = [start_i, end_i] and an integer time, return the minimum number of clips needed to cover the entire interval [0, time]. If it is impossible, return -1. Clips may overlap and be trimmed.
Input
An array clips of [start, end] intervals and an integer time.
Output
An integer: the minimum number of clips, or -1 if the window cannot be covered.
Constraints
- 1 <= clips.length <= 100
- 0 <= start_i <= end_i <= 100; 1 <= time <= 100
Examples
Example 1
Input
clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10
Output
3
Pick [0,2], [1,9], [8,10] to cover [0,10].
Example 2
Input
clips = [[0,1],[1,2]], time = 5
Output
-1
The clips cannot reach time 5.