Tập hợp khoảng rời rạc tối đa (Maximal Disjoint Intervals) trong C++

Đề bài

Cho N khoảng [l, r]. Tìm tập con lớn nhất các khoảng đôi một không giao nhau (disjoint). Hai khoảng không giao nếu không có điểm chung.

Ví dụ: {{10,20}, {23,35}, {15,21}, {37,41}} → chọn {10,20}, {23,35}, {37,41} (3 khoảng). {15,21} giao với {10,20}.

Thuật toán (Tham lam - Activity Selection)

1. Sắp xếp các khoảng theo điểm kết thúc (r) tăng dần.
2. Chọn khoảng đầu tiên. Ghi nhớ lastEnd = r của khoảng vừa chọn.
3. Duyệt các khoảng tiếp theo: nếu l > lastEnd → chọn khoảng đó, cập nhật lastEnd = r.

Chọn khoảng kết thúc sớm nhất để chừa chỗ cho nhiều khoảng sau.

Ví dụ minh họa (C++)

#include <bits/stdc++.h>
using namespace std;

bool cmp(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(), cmp);
    cout << "{" << intervals[0].first << ", " << intervals[0].second << "}\n";
    int lastEnd = intervals[0].second;
    for (size_t i = 1; i < intervals.size(); ++i) {
        if (intervals[i].first > lastEnd) {
            cout << "{" << intervals[i].first << ", " << intervals[i].second << "}\n";
            lastEnd = intervals[i].second;
        }
    }
}

int main() {
    vector<pair<int,int>> intervals = {{10,20}, {23,35}, {15,21}, {37,41}};
    cout << "Cac khoang roi rac toi da:\n";
    getMaxDisjointInterval(intervals);
    return 0;
}

Kết quả

Cac khoang roi rac toi da:
{10, 20}
{23, 35}
{37, 41}