Khâu Video trong C ++

Giả sử chúng ta có một loạt video clip từ một sự kiện thể thao kéo dài T giây. Giờ đây, những video clip này có thể chồng lên nhau và có độ dài khác nhau. Ở đây mỗi đoạn video clip [i] là một khoảng thời gian - nó bắt đầu ở đoạn [i] [0] thời gian và kết thúc ở đoạn [i] [1] thời gian. Chúng tôi có thể cắt các clip này thành các phân đoạn một cách tự do - Chúng tôi phải tìm số lượng clip tối thiểu cần thiết để chúng tôi có thể cắt các clip này thành các đoạn bao gồm toàn bộ sự kiện thể thao ([0, T]). Nếu nhiệm vụ không thể thực hiện được, hãy trả về -1. Vì vậy, nếu đầu vào là [[0,2], [4,6], [8,10], [1,9], [1,5], [5,9]] và T =10, thì đầu ra sẽ là 3, vì chúng ta có thể lấy các clip [0,2], [8,10] và [1,9], tổng cộng là 3 clip, sau đó chúng ta có thể dựng lại sự kiện thể thao như sau, chúng ta cắt [1, 9] thành các đoạn [1,2] + [2,8] + [8,9]. Bây giờ chúng ta có các phân đoạn [0,2] + [2,8] + [8,10] bao gồm sự kiện thể thao [0, 10].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Tạo một mảng v có kích thước T + 1 và điền vào mảng này với - 1

• n:=kích thước của clip

• cho tôi trong phạm vi từ 0 đến n - 1

  • if clips [i, 0]> T, sau đó chuyển sang lần lặp tiếp theo

  • v [clip [i, 0]]:=tối đa v [clip [i, 0]] và tối thiểu (clip [i, 1] và T)

• curr:=v [0]

• nếu v [0] là -1, thì trả về -1

• i:=1, ret:=1 và tiếp theo:=0

• trong khi curr

  • trong khi tôi <=curr

    • next:=max of next và v [i]

    • tăng tôi lên 1

  • nếu next =curr và next là -1, thì trả về -1

  • curr:=tiếp theo

• trả về ret khi curr> =T, nếu không thì trả về - 1

Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn

Ví dụ

#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));
}

Đầu vào

[[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]]
10

Đầu ra

3