C++でのビデオステッチ

T秒間続いたスポーツイベントの一連のビデオクリップがあるとします。これで、これらのビデオクリップを互いに重ね合わせたり、長さを変えたりすることができます。ここで、各ビデオクリップクリップ[i]は間隔です-クリップ[i] [0]時間で始まり、クリップ[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、10]をカバーするセグメント[0,2] + [2,8]+[8,10]ができました。

これを解決するには、次の手順に従います-

• サイズT+1の配列vを作成し、これに– 1

  を入力します。

• n：=クリップのサイズ

• 0からn–1の範囲のiの場合

  • 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

  • <=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