C++ में मैक्सिमल डिसजॉइंट इंटरवल्स

विवरण

N इंटरवल्स का एक सेट दिया गया है, कार्य परस्पर डिसजॉइंट इंटरवल्स का अधिकतम सेट ढूंढना है। दो इंटरवल्स [i, j] और [k, l] को डिसजॉइंट कहा जाता है यदि उनमें कोई सामान्य बिंदु नहीं है।

यदि इंटरवल्स {{10, 20}, {23, 35}, {15, 21}, {37, 41}} हैं तो अधिकतम नॉन-ओवरलैपिंग डिसजॉइंट पेयर्स हैं:

{10, 20} {23, 35} {37, 41}

ध्यान दें कि हम {15, 21} को शामिल नहीं कर सकते क्योंकि यह {10, 20} के साथ ओवरलैप करेगा।

एल्गोरिदम

1. इंटरवल्स को उनके अंत बिंदुओं के संबंध में सॉर्ट करें।
2. सभी इंटरवल्स को पार करें, यदि हमें दो ओवरलैपिंग इंटरवल्स मिलते हैं, तो निचले अंत बिंदु वाले इंटरवल को चुनें। ऐसा इंटरवल चुनने से यह सुनिश्चित होगा कि आगे के इंटरवल्स बिना किसी ओवरलैप के समायोजित हो सकते हैं।
3. सभी इंटरवल्स के लिए समान प्रक्रिया दोहराएं और उन सभी इंटरवल्स को प्रिंट करें जो इन मानदंडों को पूरा करते हैं।

उदाहरण

#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}