การต่อวิดีโอใน C++

สมมติว่าเรามีชุดวิดีโอคลิปจากการแข่งขันกีฬาที่กินเวลา T วินาที ตอนนี้คลิปวิดีโอเหล่านี้สามารถซ้อนทับกันและมีความยาวต่างกันได้ ในที่นี้ คลิปวิดีโอแต่ละคลิป[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].

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• สร้างอาร์เรย์ v ขนาด T + 1 และเติมด้วย – 1

• n :=ขนาดของคลิป

• สำหรับฉันอยู่ในช่วง 0 ถึง n – 1

  • ถ้า clips[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 and next :=0

• ในขณะที่ curr

  • ในขณะที่ฉัน <=curr

    • next :=max of next และ v[i]

    • เพิ่มขึ้น 1

  • ถ้า next =curr และถัดไปคือ -1 ให้คืนค่า -1

  • curr :=ต่อไป

• return ret เมื่อ curr>=T มิฉะนั้น return – 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