【输入样例】 10 1 8 2 7 3 4 4 2 5 5 6 1 7 9 8 3 9 10 10 6 【输出样例】 最大不相交子集：{(3,4),(5,5),(7,9),(9,10)}

这道题是经典的区间选点问题（也称为区间调度问题），可以采用贪心算法求解。具体做法是，按照区间的右端点从小到大排序，然后从左到右依次考虑每个区间，如果当前区间的左端点大于上一个区间的右端点，则选择当前区间，否则不选择。最后选择的区间构成的集合就是最大不相交子集。

以下是使用 C++ 实现的代码：

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct Interval {
    int start, end;
};

bool cmp(const Interval& a, const Interval& b) {
    return a.end < b.end; // 按照右端点从小到大排序
}

int main() {
    int n;
    cin >> n;

    vector<Interval> intervals(n);
    for (int i = 0; i < n; i++) {
        cin >> intervals[i].start >> intervals[i].end;
    }

    sort(intervals.begin(), intervals.end(), cmp);

    vector<Interval> ans;
    int last_end = 0;
    for (int i = 0; i < n; i++) {
        if (intervals[i].start > last_end) { // 找到一个不相交的区间
            ans.push_back(intervals[i]);
            last_end = intervals[i].end;
        }
    }

    cout << "最大不相交子集：{";
    for (int i = 0; i < ans.size(); i++) {
        cout << "(" << ans[i].start << "," << ans[i].end << ")";
        if (i < ans.size() - 1) {
            cout << ",";
        }
    }
    cout << "}" << endl;

    return 0;
}

输入格式为：

n
start1 end1
start2 end2
...
startn endn

例如，输入为：

10
1 8
2 7
3 4
4 2
5 5
6 1
7 9
8 3
9 10
10 6

则输出为：

最大不相交子集：{(3,4),(5,5),(7,9),(9,10)}