Maximal Disjoint Intervals ใน C++

คำอธิบาย

ได้รับชุดของ N Intervals งานคือหาชุด Maximal ของ Mutually Disjoint Intervals สอง Intervals [i, j] และ [k, l] ถือว่า Disjoint ถ้าไม่มีจุดร่วมกัน

ถ้า Intervals คือ {{10, 20}, {23, 35}, {15, 21}, {37, 41}} Maximum Non-overlapping Disjoint Pairs คือ

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

สังเกตว่าไม่สามารถรวม {15, 21} ได้ เพราะจะ Overlap กับ {10, 20}

อัลกอริทึม

1. จัดเรียง Intervals ตาม End Points
2. ท่องทุก Intervals ถ้าเจอ 2 Intervals ที่ Overlap ให้เลือก Interval ที่มี End Point น้อยกว่า การเลือกแบบนี้จะทำให้ Intervals ต่อไปสามารถใส่ได้โดยไม่ Overlap
3. ทำซ้ำขั้นตอนเดียวกันสำหรับทุก Intervals และพิมพ์ Intervals ที่ผ่านเกณฑ์

ตัวอย่างโค้ด

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