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