C ++中的视频拼接
假设我们有一个来自体育赛事的视频片段，持续了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