सी++ में वीडियो सिलाई

मान लीजिए कि हमारे पास टी सेकंड तक चलने वाले खेल आयोजन से वीडियो क्लिप की एक श्रृंखला है। अब ये वीडियो क्लिप एक-दूसरे से ओवरलैप हो सकते हैं और इनकी लंबाई अलग-अलग हो सकती है। यहां प्रत्येक वीडियो क्लिप क्लिप [i] एक अंतराल है - यह क्लिप [i] [0] समय पर शुरू होती है और क्लिप [i] [1] समय पर समाप्त होती है। हम इन क्लिप को खंडों में स्वतंत्र रूप से काट सकते हैं - हमें आवश्यक क्लिप की न्यूनतम संख्या का पता लगाना होगा ताकि हम क्लिप को उन खंडों में काट सकें जो पूरे खेल आयोजन ([0, टी]) को कवर करते हैं। यदि कार्य असंभव है, तो वापसी -1। तो अगर इनपुट [[0,2], [4,6], [8,10], [1,9], [1,5], [5,9]], और टी =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] को कवर कर रहे हैं।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• T + 1 आकार का एक सरणी v बनाएं और इसे - 1 से भरें

• n :=क्लिप का आकार

• मैं के लिए 0 से n - 1 की सीमा में

  • अगर क्लिप[i, 0]> T, तो अगले पुनरावृत्ति पर जाएं

  • v[क्लिप्स[i, 0]] :=अधिकतम v[क्लिप्स[i, 0]] और न्यूनतम (क्लिप[i, 1] और T)

• वर्तमान:=वी[0]

• अगर v[0] -1 है, तो -1 लौटें

• मैं :=1 , रिट :=1 और अगला :=0

• जबकि करंट <टी और मैं <=n

  • जबकि मैं <=curr

    • अगला:=अगले का अधिकतम और v[i]

    • 1 से बढ़ाएँ

  • अगर अगला =curr और अगला -1 है, तो वापसी -1

  • वर्तमान:=अगला

• वापसी रिट जब curr>=T, अन्यथा वापसी – 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