作者：萍子WYP | 来源：互联网 | 2024-12-19 19:46
在活动选择问题中，我们有一个包含n个活动的集合E={1,2,...,n}，每个活动都需要使用同一资源（例如演讲会场），且在同一时间内只能有一个活动占用该资源。每个活动i都有一个起始时间s_i和结束时间f_i，并且s_i
目标是从这些活动中选择出最大的相容活动子集。为了实现这一目标，我们可以采用贪心算法。具体步骤如下：
1. 首先对所有活动按照结束时间f_i进行升序排序。
2. 选择第一个活动作为初始活动，并记录其结束时间。
3. 依次检查后续活动，如果某个活动的起始时间大于或等于当前记录的结束时间，则选择该活动，并更新结束时间为该活动的结束时间。
4. 重复上述过程直到遍历完所有活动。
以下是C++代码实现：
```cpp
#include
using namespace std;
const int N = 2e5 + 100;
struct Activity {
int start, end;
bool operator<(const Activity &other) const {
return end }
};
int main() {
int n;
cin >> n;
vector activities(n);
for (int i = 0; i cin >> activities[i].start >> activities[i].end;
}
sort(activities.begin(), activities.end());
int count = 0;
int last_end = -1;
for (const auto &act : activities) {
if (act.start >= last_end) {
++count;
last_end = act.end;
}
}
cout < return 0;
}
```
这段代码首先定义了一个结构体`Activity`来存储每个活动的起始时间和结束时间，并重载了小于运算符以便按结束时间排序。然后通过读取输入数据并进行排序，最后利用贪心算法选择尽可能多的相容活动。
![扫描线三巨头 hdu1928hdu 1255 hdu 1542 [POJ 1151]](https://img.php1.cn/3c972/245b5/42f/19446f78530d3747.jpeg)
京公网安备 11010802041100号