मान लीजिए हमारे पास इंटरवल्स का एक संग्रह है। हमें न्यूनतम संख्या में इंटरवल्स हटाने हैं ताकि शेष इंटरवल्स गैर-ओवरलैपिंग (non-overlapping) हों।
उदाहरण: [[1,2],[2,3],[3,4],[1,3]] → आउटपुट 1 ([1,3] हटाएँ)।
लालची एल्गोरिदम (अंत समय द्वारा सॉर्ट)
n = सरणी का आकार। यदि 0, तो 0 लौटाएँ।count = 1(पहला इंटरवल हमेशा रखें)।- सरणी को अंत समय (
end) के आधार पर सॉर्ट करें। end = पहले इंटरवल का अंत।- प्रत्येक इंटरवल
i = 1 से n-1के लिए:- यदि
arr[i][0] >= end(ओवरलैप नहीं):end = arr[i][1],count++।
- यदि
n - countलौटाएँ (हटाए जाने वाले इंटरवल्स)।
C++ कार्यान्वयन
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
static bool cmp(vector<int>& a, vector<int>& b) {
return a[1] < b[1];
}
int eraseOverlapIntervals(vector<vector<int>>& arr) {
int n = arr.size();
if (!n) return 0;
int cnt = 1;
sort(arr.begin(), arr.end(), cmp);
int end = arr[0][1];
for (int i = 1; i < n; i++) {
if (arr[i][0] >= end) {
end = arr[i][1];
cnt++;
}
}
return n - cnt;
}
};
int main() {
vector<vector<int>> v = {{1,2},{1,2},{1,2}};
Solution ob;
cout << ob.eraseOverlapIntervals(v); // 2
return 0;
}
इनपुट
[[1,2],[1,2],[1,2]]
आउटपुट
2