【输入样例】 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++实现
时间: 2024-01-02 10:04:35 浏览: 20
这是一个经典的区间调度问题,可以使用贪心算法来解决。
C++代码如下:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Interval {
int start;
int end;
Interval() : start(0), end(0) {}
Interval(int s, int e) : start(s), end(e) {}
};
bool cmp(const Interval& a, const Interval& b) {
return a.end < b.end;
}
vector<Interval> maxNonOverlapSet(vector<Interval>& intervals) {
vector<Interval> res;
if (intervals.empty()) {
return res;
}
sort(intervals.begin(), intervals.end(), cmp);
res.push_back(intervals[0]);
for (int i = 1; i < intervals.size(); i++) {
if (intervals[i].start >= res.back().end) {
res.push_back(intervals[i]);
}
}
return res;
}
int main() {
int n;
cin >> n;
vector<Interval> intervals;
for (int i = 0; i < n; i++) {
int start, end;
cin >> start >> end;
intervals.push_back(Interval(start, end));
}
vector<Interval> res = maxNonOverlapSet(intervals);
cout << "最大不相交子集:{";
for (int i = 0; i < res.size(); i++) {
cout << "(" << res[i].start << "," << res[i].end << ")";
if (i != res.size() - 1) {
cout << ",";
}
}
cout << "}" << endl;
return 0;
}
```
输入样例:
```
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)}
```