假设我们有一个来自体育赛事的视频片段，持续了T秒。现在，这些视频剪辑可以彼此重叠并且具有不同的长度。这里，每个视频片段clips [i]是一个间隔−它始于clips [i] [0]时间，结束于clips [i] [1]时间。我们可以自由地将这些片段剪切成片段-我们必须找到所需片段的最少数量，以便我们可以将片段剪切成覆盖整个体育赛事（[0，T]）的片段。如果无法完成任务，则返回-1。因此，如果输入类似于[[0,2]，[4,6]，[8,10]，[1,9]，[1,5]，[5,9]]，并且T = 10，则输出为3，因为我们可以截取片段[0,2]，[8,10]和[1,9]，总共3个片段，那么我们可以按如下方式重构体育赛事，我们将[1， 9]划分为[1,2] + [2,8] + [8,9]段。现在我们有了细分[0,2] + [2,8] + [8,10]，它们涵盖了体育赛事[0，
为了解决这个问题，我们将遵循以下步骤-
创建大小为T + 1的数组v，并用– 1填充它
n：=片段大小
对于i，范围为0至n – 1
如果clips [i，0]> T，则跳至下一个迭代
v [clips [i，0]]：= v [clips [i，0]]的最大值和（clips [i，1]和T）的最小值
curr：= v [0]
如果v [0]为-1，则返回-1
i：= 1，ret：= 1和next：= 0
而curr <T和i <= n
下一个：=下一个和v [i]的最大值
使我增加1
而我<= curr
如果next = curr并且next为-1，则返回-1
curr：=下一个
当curr> = T时返回ret，否则返回– 1
让我们看一下下面的实现以获得更好的理解
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int videoStitching(vector<vector<int>>& clips, int T) {
vector <int> v(T + 1, -1);
int n = clips.size();
for(int i = 0; i < n; i++){
if(clips[i][0] > T)continue;
v[clips[i][0]] = max(v[clips[i][0]], min(clips[i][1],
T));
}
int curr = v[0];
if(v[0] == -1)return -1;
int i = 1;
int ret = 1;
int next = 0;
while(curr < T && i <= n){
while(i <= curr){
next = max(next, v[i]);
i++;
}
if(next == curr || next == -1) return -1;
curr = next;
ret++;
}
return curr >= T? ret : -1;
}
};
main(){
vector<vector<int>> v1 = {{0,2},{4,6},{8,10},{1,9},{1,5},{5,9}};
Solution ob;
cout << (ob.videoStitching(v1, 10));
}[[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]] 10
输出结果
3