Loading problem...
You are given a collection of time intervals representing recorded segments from a live event that lasted exactly duration units of time. Each interval is represented as a pair [startᵢ, endᵢ], indicating that the segment begins at time startᵢ and concludes at time endᵢ. These intervals may overlap with each other and have varying lengths.
The goal is to select the minimum number of intervals from the given collection such that their union completely covers the entire event duration from time 0 to time duration (inclusive of 0, up to but covering duration).
Key Insight: Any selected interval can be conceptually "trimmed" to only use the portion needed for coverage. For instance, an interval [1, 8] can contribute coverage for any subrange like [3, 5] or [1, 4] as part of the solution.
Return the minimum number of intervals required to achieve complete coverage of the range [0, duration]. If it is impossible to cover the entire duration with the given intervals, return -1.
clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]]
time = 103We select the intervals [0,2], [1,9], and [8,10], totaling 3 intervals. From [1,9], we use the portion [2,8] to bridge between [0,2] and [8,10]. The combined coverage becomes: [0,2] → [2,8] → [8,10], which fully covers [0, 10].
clips = [[0,1],[1,2]]
time = 5-1The available intervals [0,1] and [1,2] can only cover up to time 2. There is no way to cover the range [0, 5] with these intervals, so we return -1.
clips = [[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6,7],[1,3],[4,7],[1,4],[2,5],[2,6],[3,4],[4,5],[5,7],[6,9]]
time = 93We can select intervals [0,4], [4,7], and [6,9]. The interval [0,4] covers [0,4], [4,7] extends coverage to [4,7], and [6,9] completes the coverage to [9]. This achieves full coverage with just 3 intervals.
Constraints