समस्या विवरण
मान लीजिए हमारे पास संभावित रूप से ओवरलैपिंग अंतरालों (समावेशी) की एक सूची है। अब एक ऑपरेशन पर विचार करें जहां हम एक अंतराल हटाते हैं, फिर शेष अंतरालों को मर्ज करते हैं और फिर बचे हुए अंतरालों की संख्या गिनते हैं। हमें हटाने के बाद बचे हुए अंतरालों की अधिकतम संभव संख्या ढूंढनी है।
उदाहरण के लिए, यदि इनपुट है intervals = [[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] को हटाना सही है।
हल करने का दृष्टिकोण
इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:
- संख्या जोड़ियों का एक ऐरे memo परिभाषित करें
- एक फंक्शन countIntervals() परिभाषित करें जो एक 2D ऐरे intervals, i, end लेता है
- यदि i, intervals के आकार के बराबर है, तो 0 वापस करें
- यदि memo[i].first < end, तो -अनंत वापस करें
- यदि memo[i].first == end, तो memo[i].second वापस करें
- यदि end < intervals[i][0]:
- memo[i] := min(end, memo[i].first), 1 + countIntervals(intervals, i+1, intervals[i][1])
- memo[i].second वापस करें
- memo[i] := min(end, memo[i].first), countIntervals(intervals, i+1, max(intervals[i][1], end))
- memo[i].second वापस करें
- मुख्य विधि से:
- memo ऐरे को intervals के आकार तक रिसाइज करें
- intervals ऐरे को सॉर्ट करें
- count := 0, result := 0, end := -1
- एक ऐरे temp परिभाषित करें
- i := 0 से intervals के आकार तक:
- result := max(result, count + countIntervals(intervals, i+1, end))
- यदि end < intervals[i][0], तो count बढ़ाएं
- end := max(end, intervals[i][1])
- result वापस करें
उदाहरण
#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
