मान लीजिए कि हमारे पास अंतराल (समावेशी) की एक सूची है जो संभावित रूप से अतिव्यापी हैं। अब विचार करें कि एक ऑपरेशन है जहां हम एक अंतराल को हटाते हैं, फिर शेष अंतराल को मर्ज करते हैं और फिर बचे हुए अंतरालों की संख्या की गणना करते हैं। हमें हटाने के बाद अधिकतम बचे हुए अंतरालों की संख्या ज्ञात करनी होगी।
इसलिए, यदि इनपुट अंतराल की तरह है =[ [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] को हटाना सही है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
संख्या युग्मों के सरणी मेमो को परिभाषित करें,
-
एक फ़ंक्शन काउंटइंटरवल्स () को परिभाषित करें, इसमें एक 2D सरणी अंतराल, i, अंत लगेगा।
-
यदि i अंतरालों के आकार के समान है, तो -
-
वापसी 0
-
-
अगर मेमो[i].first_element <अंत, फिर -
-
वापसी -अनंत।
-
-
अगर memo[i].first_element अंत के समान है, तो -
-
मेमो का दूसरा तत्व लौटाएं[i]
-
-
अगर अंत <अंतराल[i, 0], तो -
-
मेमो [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, अंत)
-
अगर अंत <अंतराल[i, 0], तो -
-
(गिनती 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