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. अन्तে স্টকে মার্জড ইন্টারভালগুলো থাকবে।

উদাহরণ কোড

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

struct interval {
    int start;
    int 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}