You are given a series of video clips from a sporting event that lasted T seconds. These video clips can be overlapping with each other and have varied lengths.
Each video clip clips[i] is an interval: it starts at time clips[i][0] and ends at time clips[i][1]. 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, T]). If the task is impossible, return -1.
Example 1:
Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], T = 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:
Input: clips = [[0,1],[1,2]], T = 5 Output: -1 Explanation: We can't cover [0,5] with only [0,1] and [0,2]. Example 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]], T = 9 Output: 3 Explanation: We can take clips [0,4], [4,7], and [6,9]. Example 4:
Input: clips = [[0,4],[2,8]], T = 5 Output: 2 Explanation: Notice you can have extra video after the event ends.
Note:
1 <= clips.length <= 100 0 <= clips[i][0], clips[i][1] <= 100 0 <= T <= 100
[[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]] 10 [[0,1],[1,2]] 5 [[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]] 9 [0,4],[2,8]] 5 [[0,5],[1,6],[2,7],[3,8],[4,9],[5,10],[6,11],[7,12],[8,13],[9,14],[10,15],[11,16],[12,17],[13,18],[14,19],[15,20],[16,21],[17,22],[18,23],[19,24],[20,25],[21,26],[22,27],[23,28],[24,29],[25,30],[26,31],[27,32],[28,33],[29,34],[30,35],[31,36],[32,37],[33,38],[34,39],[35,40],[36,41],[37,42],[38,43],[39,44],[40,45],[41,46],[42,47],[43,48],[44,49],[45,50],[46,51],[47,52],[48,53],[49,54]] 50
// 4ms, 69%
class Solution {
public:
int videoStitching(vector<vector<int>>& clips, int T) {
sort(clips.begin(), clips.end());
int idx = 0, end = 0, res = 0;
for (int i = 0; i < clips.size();) {
// pick one that can take us the farthest
while (i < clips.size() && clips[i][0] <= idx) {
end = max(end, clips[i][1]);
i++;
}
if (idx == end) return -1;
res++;
if (end >= T) break;
idx = end;
}
return end >= T? res : -1;
}
};
// 812ms, 7%
class Solution {
int check(const vector<vector<int>>& clips, int i, int used, int beg, int end, vector<int>& dp) {
if (i >= clips.size()) {
return INT_MAX;
}
int idx = i;
if (dp[i] > 0 && dp[i] <= used + 1)
return dp[i];
int res = INT_MAX;
while (i < clips.size()) {
const auto& cc = clips[i];
if (cc[0] <= beg && cc[1] >= end)
return used + 1;
if (cc[0] > beg)
break;
res = min(res, check(clips, i+1, used+1, cc[1], end, dp));
i++;
}
dp[idx] = res;
return res;
}
public:
int videoStitching(vector<vector<int>>& clips, int T) {
sort(clips.begin(), clips.end(), [](const auto& a, const auto& b) {
return a[0] < b[0] || (a[0] == b[0] && a[1] < b[1]);
});
vector<int> dp(clips.size(), -1);
int r = check(clips, 0, 0, 0, T, dp);
return r != INT_MAX? r : -1;
}
};```