विवरण
एन अंतरालों के एक सेट को देखते हुए, कार्य पारस्परिक रूप से असंबद्ध अंतरालों के अधिकतम सेट को खोजना है। दो अंतराल [i, j] और [k,l] को असंयुक्त कहा जाता है यदि उनमें कोई बिंदु उभयनिष्ठ न हो
यदि अंतराल {{10, 20} {23, 35}, {15, 21}, {37, 41}} हैं तो अधिकतम गैर-अतिव्यापी असंबद्ध जोड़े हैं -
{10, 20}
{23, 35}
{37, 41} ध्यान दें कि हम {15, 21} को शामिल नहीं कर सकते क्योंकि यह {10, 20}
. के साथ ओवरलैप हो जाएगाएल्गोरिदम
1. Sort the intervals, with respect to their end points. 2. Traverse the all intervals, if we get two overlapping intervals, then choose the interval with lower end point. Choosing such interval will ensure that intervals further can be accommodated without any overlap 3. Repeat the same procedure for all the intervals and print all the intervals which satisfy these criteria
उदाहरण
#include <bits/stdc++.h>
using namespace std;
bool sortFun(pair<int, int> &a, pair<int, int> &b){
return (a.second < b.second);
}
void getMaxDisjointInterval(vector<pair<int, int>> intervals){
sort(intervals.begin(), intervals.end(), sortFun);
cout << "{" << intervals[0].first << ", " << intervals[0].second << "}\n";
int r1 = intervals[0].second;
for (int i = 1; i < intervals.size(); ++i) {
int l1 = intervals[i].first;
int r2 = intervals[i].second;
if (l1 > r1) {
cout << "{" << l1 << ", " << r2 << "}\n";
r1 = r2;
}
}
}
int main(){
int n = 4;
vector<pair<int, int>> intervals = {
{10, 20},
{23, 35},
{15, 21},
{37, 41}
};
cout << "Max disjoint pairs are:\n";
getMaxDisjointInterval(intervals);
return 0;
} आउटपुट
जब आप उपरोक्त प्रोग्राम को संकलित और निष्पादित करते हैं। यह निम्न आउटपुट उत्पन्न करता है -
Max disjoint pairs are:
{10, 20}
{23, 35}
{37, 41}