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}