C++ এ ভিডিও স্টিচিং

ধরুন আমাদের কাছে একটি ক্রীড়া ইভেন্টের ভিডিও ক্লিপগুলির একটি সিরিজ রয়েছে যা টি সেকেন্ড স্থায়ী হয়েছিল। এখন এই ভিডিও ক্লিপগুলি একে অপরের সাথে ওভারল্যাপ করা যেতে পারে এবং বিভিন্ন দৈর্ঘ্যের হতে পারে। এখানে প্রতিটি ভিডিও ক্লিপ ক্লিপ[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,2] + [2,8] + [8,10] যা ক্রীড়া ইভেন্টকে কভার করছে [0, 10]।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• T + 1 আকারের একটি অ্যারে তৈরি করুন এবং এটি – 1

  দিয়ে পূরণ করুন

• n :=ক্লিপগুলির আকার

• 0 থেকে n – 1

  রেঞ্জের i জন্য

  • যদি ক্লিপ[i, 0]> T হয়, তাহলে পরবর্তী পুনরাবৃত্তিতে চলে যান

  • v[clips[i, 0]] :=v[clips[i, 0]] এর সর্বোচ্চ এবং (ক্লিপ[i, 1] এবং T) এর সর্বনিম্ন

• curr :=v[0]

• যদি v[0] -1 হয়, তাহলে -1 ফেরত দিন

• i :=1, ret :=1 এবং পরবর্তী :=0

• যখন curr

  • যখন আমি <=curr

    • পরবর্তী :=পরবর্তী এবং v[i]

      -এর সর্বোচ্চ

    • i 1 দ্বারা বাড়ান

  • যদি next =curr এবং পরবর্তী হয় -1, তাহলে ফিরুন -1

  • curr :=পরবর্তী

• রিটার্ন ret যখন 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