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에 대해
- 클립[i, 0]> T인 경우 다음 반복으로 건너뜁니다.
- v[clips[i, 0]] :=v[clips[i, 0]]의 최대값 및 (clips[i, 1] 및 T)의 최소값
커 :=v[0]
v[0]이 -1이면 -1을 반환합니다.
i :=1, ret :=1 및 다음 :=0
동안 curr
- 동안 나는 <=커
  - 다음 :=다음 및 v[i]
    의 최대값
  - i를 1 증가
- 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