C++ में वीडियो स्टिचिंग (Video Stitching)

मान लीजिए हमारे पास एक खेल आयोजन के वीडियो क्लिप्स की श्रृंखला है जो T सेकंड तक चला। ये वीडियो क्लिप्स एक-दूसरे के साथ ओवरलैप हो सकते हैं और इनकी लंबाई विविध होती है। यहां प्रत्येक वीडियो क्लिप clips[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] को कवर करते हैं।

समाधान दृष्टिकोण

आकार T+1 का एक ऐरे v बनाएं, -1 से भरें
प्रत्येक क्लिप के लिए, v[clips[i][0]] को max(v[clips[i][0]], min(clips[i][1], T)) से अपडेट करें
curr := v[0] से शुरू करें, यदि -1 है तो -1 लौटाएं
लालची दृष्टिकोण से अगले सर्वोत्तम पहुंच बिंदु को ट्रैक करते हुए क्लिप्स गिनें
यदि curr ≥ T तो ret लौटाएं, अन्यथा -1

C++ कार्यान्वयन

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

int main(){ 
    vector<vector<int>> v1 = {{0,2},{4,6},{8,10},{1,9},{1,5},{5,9}}; 
    Solution ob; 
    cout << (ob.videoStitching(v1, 10)); 
    return 0; 
}

इनपुट

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