Problem

You are given a series of video clips from a sporting event that lasted time seconds. These video clips can be overlapping with each other and have varying lengths.

Each video clip is described by an array clips where clips[i] = [starti, endi] indicates that the ith clip started at starti and ended at endi.

We can cut these clips into segments freely.

  • For example, a clip [0, 7] can be cut into segments [0, 1] + [1, 3] + [3, 7].

Return the minimum number of clips needed so that we can cut the clips into segments that cover the entire sporting event [0, time]. If the task is impossible, return -1.

Examples

Example 1

1
2
3
4
5
6

Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], time = 10
Output: 3
Explanation: We take the clips [0,2], [8,10], [1,9]; a total of 3 clips.
Then, we can reconstruct the sporting event as follows:
We cut [1,9] into segments [1,2] + [2,8] + [8,9].
Now we have segments [0,2] + [2,8] + [8,10] which cover the sporting event [0, 10].

Example 2

1
2
3

Input: clips = [[0,1],[1,2]], time = 5
Output: -1
Explanation: We cannot cover [0,5] with only [0,1] and [1,2].

Example 3

1
2
3

Input: 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 = 9
Output: 3
Explanation: We can take clips [0,4], [4,7], and [6,9].

Constraints

  • 1 <= clips.length <= 100
  • 0 <= starti <= endi <= 100
  • 1 <= time <= 100

Solution

Method 1 – Greedy Interval Covering

Intuition

To cover the interval [0, time] with the minimum number of clips, we use a greedy approach: always pick the clip that extends coverage the farthest among those starting before or at the current end. This is similar to the Jump Game II or interval covering problems.

Approach

  1. Sort clips by their start time.
  2. Initialize variables for the current end of coverage and the next farthest end.
  3. Iterate through clips, for each, if its start is within the current coverage, update the farthest end.
  4. When reaching the end of current coverage, increment the answer and update coverage to the farthest end.
  5. If at any point the next clip starts after the current coverage, return -1.
  6. Continue until coverage reaches or exceeds time.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    int videoStitching(vector<vector<int>>& clips, int time) {
        sort(clips.begin(), clips.end());
        int ans = 0, end = 0, far = 0, i = 0, n = clips.size();
        while (end < time) {
            while (i < n && clips[i][0] <= end) {
                far = max(far, clips[i][1]);
                i++;
            }
            if (far == end) return -1;
            ans++;
            end = far;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

import "sort"
func videoStitching(clips [][]int, time int) int {
    sort.Slice(clips, func(i, j int) bool { return clips[i][0] < clips[j][0] })
    ans, end, far, i, n := 0, 0, 0, 0, len(clips)
    for end < time {
        for i < n && clips[i][0] <= end {
            if clips[i][1] > far { far = clips[i][1] }
            i++
        }
        if far == end { return -1 }
        ans++
        end = far
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

import java.util.*;
class Solution {
    public int videoStitching(int[][] clips, int time) {
        Arrays.sort(clips, Comparator.comparingInt(a -> a[0]));
        int ans = 0, end = 0, far = 0, i = 0, n = clips.length;
        while (end < time) {
            while (i < n && clips[i][0] <= end) {
                far = Math.max(far, clips[i][1]);
                i++;
            }
            if (far == end) return -1;
            ans++;
            end = far;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun videoStitching(clips: Array<IntArray>, time: Int): Int {
        clips.sortBy { it[0] }
        var ans = 0; var end = 0; var far = 0; var i = 0; val n = clips.size
        while (end < time) {
            while (i < n && clips[i][0] <= end) {
                far = maxOf(far, clips[i][1])
                i++
            }
            if (far == end) return -1
            ans++
            end = far
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def videoStitching(clips: list[list[int]], time: int) -> int:
    clips.sort()
    ans = end = far = i = 0
    n = len(clips)
    while end < time:
        while i < n and clips[i][0] <= end:
            far = max(far, clips[i][1])
            i += 1
        if far == end:
            return -1
        ans += 1
        end = far
    return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

impl Solution {
    pub fn video_stitching(clips: Vec<Vec<i32>>, time: i32) -> i32 {
        let mut clips = clips;
        clips.sort_by_key(|x| x[0]);
        let (mut ans, mut end, mut far, mut i, n) = (0, 0, 0, 0, clips.len());
        while end < time {
            while i < n && clips[i][0] <= end {
                far = far.max(clips[i][1]);
                i += 1;
            }
            if far == end { return -1; }
            ans += 1;
            end = far;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    videoStitching(clips: number[][], time: number): number {
        clips.sort((a, b) => a[0] - b[0]);
        let ans = 0, end = 0, far = 0, i = 0, n = clips.length;
        while (end < time) {
            while (i < n && clips[i][0] <= end) {
                far = Math.max(far, clips[i][1]);
                i++;
            }
            if (far === end) return -1;
            ans++;
            end = far;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n), due to sorting and linear scan.
  • 🧺 Space complexity: O(1), only a constant number of variables are used.