C++ में ओवरलैपिंग अंतराल मर्ज करना

समस्या कथन

किसी भी क्रम में समय अंतराल का एक सेट दिया गया है, सभी ओवरलैपिंग अंतराल को एक में मर्ज करें और परिणाम आउटपुट करें जिसमें केवल पारस्परिक रूप से अनन्य (mutually exclusive) अंतराल हों।

दिए गए अंतराल सेट {{12, 14}, {11, 13}, {20, 22}, {21, 23}} के लिए:

• अंतराल {12, 14} और {11, 13} एक दूसरे को ओवरलैप करते हैं, इसलिए उन्हें {11, 14} के रूप में मर्ज करें
• अंतराल {20, 22} और {21, 23} एक दूसरे को ओवरलैप करते हैं, इसलिए उन्हें {20, 23} के रूप में मर्ज करें

एल्गोरिदम

1. अंतराल को प्रारंभ समय के बढ़ते क्रम के आधार पर सॉर्ट करें
2. पहले अंतराल को स्टैक पर पुश करें
3. प्रत्येक अंतराल के लिए नीचे दिए गए चरण करें:
   3.1. यदि वर्तमान अंतराल स्टैक के शीर्ष के साथ ओवरलैप नहीं करता, तो इसे पुश करें।
   3.2. यदि वर्तमान अंतराल स्टैक के शीर्ष के साथ ओवरलैप करता है और वर्तमान अंतराल का अंत समय शीर्ष से अधिक है, तो स्टैक शीर्ष को वर्तमान अंतराल के अंत समय से अपडेट करें।
4. अंत में, स्टैक में मर्ज किए गए अंतराल होते हैं।

C++ उदाहरण

#include <iostream>
#include <algorithm>
#include <stack>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;

struct Interval {
    int start, end;
};

bool compareInterval(Interval i1, Interval i2) {
    return (i1.start < i2.start);
}

void mergeOverlappingIntervals(Interval *arr, int n) {
    if (n <= 0) return;
    stack<Interval> s;
    sort(arr, arr + n, compareInterval);
    s.push(arr[0]);
    for (int i = 1; i < n; ++i) {
        Interval top = s.top();
        if (top.end < arr[i].start)
            s.push(arr[i]);
        else if (top.end < arr[i].end) {
            top.end = arr[i].end;
            s.pop();
            s.push(top);
        }
    }
    cout << "Merged intervals: " << endl;
    while (!s.empty()) {
        Interval i = s.top();
        cout << "{" << i.start << ", " << i.end << "}" << " ";
        s.pop();
    }
    cout << endl;
}

int main() {
    Interval arr[] = {{12, 14}, {11, 13}, {20, 22}, {21, 23}};
    mergeOverlappingIntervals(arr, SIZE(arr));
    return 0;
}

आउटपुट

Merged intervals: {20, 23} {11, 14}