ধরুন আমাদের কাছে অন্তর্বর্তীগুলির একটি তালিকা রয়েছে (অন্তর্ভুক্ত) যা সম্ভাব্য ওভারল্যাপিং। এখন বিবেচনা করুন যে একটি অপারেশন আছে যেখানে আমরা একটি ব্যবধান মুছে ফেলি, তারপর অবশিষ্ট ব্যবধানগুলিকে একত্রিত করি এবং তারপরে অবশিষ্ট বিরতির সংখ্যা গণনা করি। অপসারণের পরে আমাদের সর্বোচ্চ সংখ্যক অবশিষ্ট বিরতি খুঁজে বের করতে হবে।
সুতরাং, যদি ইনপুটটি ইন্টারভালের মত হয় =[ [5, 8], [6, 7], [7, 10], [9, 11]], তাহলে আউটপুট হবে 2। কারণ −
-
যদি আমরা ব্যবধান [5, 8] মুছে ফেলি তাহলে আমরা মার্জ হিসাবে [6, 11] পাব।
-
যদি আমরা ব্যবধান [6, 7] মুছে ফেলি তাহলে আমরা মার্জ হিসাবে [5, 11] পাব।
-
যদি আমরা ব্যবধান [7, 10] মুছে ফেলি তবে আমরা মার্জ হিসাবে [5, 8], [9, 11] পাব।
-
যদি আমরা ব্যবধান [9, 11] মুছে ফেলি তাহলে আমরা মার্জ হিসাবে [5, 10] পাব।
সুতরাং [7, 10] অপসারণ করা নিখুঁত।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
সংখ্যা জোড়ার একটি অ্যারে মেমো সংজ্ঞায়িত করুন,
-
একটি ফাংশন countIntervals(), এটি একটি 2D অ্যারে বিরতি নেবে, i, end।
-
যদি আমি অন্তরের আকারের সমান হয়, তাহলে −
-
রিটার্ন 0
-
-
যদি memo[i].first_element
-
রিটার্ন −ইনফিনিটি।
-
-
যদি memo[i].first_element শেষের মত হয়, তাহলে −
-
মেমো[i]
এর দ্বিতীয় উপাদান ফেরত দিন
-
-
যদি শেষ হয়
-
memo[i] :=সর্বনিম্ন শেষ এবং মেমোর প্রথম [i], 1 + কাউন্টইন্টারভাল(ব্যবধান, i + 1, ব্যবধান[i, 1])
-
মেমো[i]
এর দ্বিতীয় উপাদান ফেরত দিন
-
-
মেমো[i] :=মেমো[i] এবং কাউন্টইন্টারভালের সর্বনিম্ন শেষ এবং প্রথম উপাদান(ব্যবধান, i + 1, সর্বাধিক ব্যবধান[I, 1] এবং শেষ)
-
মেমো[i]
এর দ্বিতীয় মান ফেরত দিন
-
-
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
-
ব্যবধানের আকারে অ্যারে মেমোর আকার পরিবর্তন করুন
-
অ্যারের ব্যবধানগুলি সাজান
-
গণনা :=0, ফলাফল :=0, শেষ :=− 1
-
একটি অ্যারের তাপমাত্রা সংজ্ঞায়িত করুন
-
i এর জন্য :=0 থেকে i <ব্যবধানের আকার, আপডেট (i 1 দ্বারা বাড়ান), করবেন −
-
ফলাফল :=সর্বাধিক ফলাফল এবং গণনা + গণনা অন্তর (ব্যবধান, i + 1, শেষ)
-
যদি শেষ হয়
-
(গণনা 1 দ্বারা বৃদ্ধি করুন)
-
-
শেষ :=শেষ এবং ব্যবধানের সর্বাধিক [i, 1]
-
-
ফেরত ফলাফল
-
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> memo;
int countIntervals(vector<vector<int>>& intervals, int i, int end) {
if (i == intervals.size()) return 0;
if (memo[i].first < end)
return INT_MIN;
if (memo[i].first == end)
return memo[i].second;
if (end < intervals[i][0]) {
memo[i] = {min(end, memo[i].first), 1 +
countIntervals(intervals, i + 1, intervals[i][1])};
return memo[i].second;
}
memo[i] = {min(end, memo[i].first),
countIntervals(intervals, i + 1, max(intervals[i][1],
end))};
return memo[i].second;
}
int solve(vector<vector<int>>& intervals) {
memo.clear();
memo.resize(intervals.size(), {INT_MAX, −1});
sort(intervals.begin(), intervals.end());
int count = 0, result = 0, end = −1;
vector<int> temp;
for (int i = 0; i < intervals.size(); i++) {
result = max(result, count + countIntervals(intervals, i + 1,
end));
if (end < intervals[i][0])
count++;
end = max(end, intervals[i][1]);
}
return result;
}
int main(){
vector<vector<int>> v = {{5, 8}, {6, 7}, {7, 10}, {9, 11}};
cout<<solve(v);
} ইনপুট
{{5, 8}, {6, 7}, {7, 10}, {9, 11}} আউটপুট
2
