数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究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, 10]。
为了解决这个问题，我们将遵循以下步骤 -
创建一个大小为 T + 1 的数组 v，并将其填充为 – 1
n := clips 的大小
对于 i 从 0 到 n – 1 的范围
如果 clips[i, 0] > T，则跳到下一个迭代
v[clips[i, 0]] := v[clips[i, 0]] 和 min(clips[i, 1] 和 T) 的最大值
curr := v[0]
如果 v[0] 为 -1，则返回 -1
i := 1，ret := 1 且 next := 0
当 curr < T 且 i <= n 时
当 i <= curr 时
next := next 和 v[i] 的最大值
将 i 增加 1
如果 next = curr 且 next 为 -1，则返回 -1
curr := next
当 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
205 次查看
