মান লেযিয়ে একটি খেলার ইভেন্ট 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 হলে আউটপুট হবে ৩, কারণ আমরা [0,2], [8,10] এবং [1,9] ক্লিপগুলো নিতে পারি, মোট ৩টি। এরপর [1,9]-কে [1,2] + [2,8] + [8,9] সেগমেন্টে কাটলে পাব [0,2] + [2,8] + [8,10] যা [0, 10] কভার করে।
এটি সমাধান করার জন্য আমরা নিচের ধাপগুলো অনুসরণ করব -
T+1 আকারের একটি v অ্যারে তৈরি করুন, -1 দিয়ে পূরণ করুন
n := clips.size()
i = 0 থেকে n-1 পর্যন্ত লুপ চালান
যদি clips[i][0] > T হয়, পরবর্তী ইটারেশনে যান
v[clips[i][0]] := max(v[clips[i][0]], min(clips[i][1], T))
curr := v[0]
যদি v[0] == -1 হয়, -1 রিটার্ন করুন
i := 1, ret := 1, next := 0
যখন curr < T এবং i <= n
যখন i <= curr
next := max(next, v[i])
i++ করুন
যদি next == curr এবং next == -1 হয়, -1 রিটার্ন করুন
curr := next, ret++
যদি curr >= T হয় ret রিটার্ন করুন, অন্যথায় -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
