贪心法之活动安排问题

问题:

????????????????给定n个活动，每个活动有一个开始时间si和结束时间fi，选择出最大的互不相容的活动? ? ?集合。

思路：? ? ?

1. 将所有活动按照结束时间从小到大排序。

2. 选择第一个活动，并将其加入最终的选择集合中。

3. 依次考虑剩余的活动，如果当前活动的开始时间晚于等于上一个已选活动的结束时间，则将该活动加入最终的选择集合中。

4. 重复步骤3，直到所有活动都被考虑完毕。

5. 输出最终的选择集合。

示例:

按照右端点从小到大排序后的顺序为：

? ? ? ? ? ? ? ? ?区间1:?[1,?4]
? ? ? ? ? ? ? ? ?区间2:?[3,?6]
? ? ? ? ? ? ? ? ?区间3:?[5,?7]

按照区间调度算法进行选择，具体步骤如下：

首先选择右端点最小的区间1?[1,?4]，更新preEnd为4。
接着剩下区间2?[3,?6]?的起始位置小于preEnd，无法选择。
最后剩下的区间3?[5,?7]?的起始位置大于preEnd，可以选择。
选中的区间序号为1和3，选中的区间个数为2。

所以最优解是选择区间1和3。

代码:

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

using namespace std;

int main() {
    // 读取活动数量
    int n;
    cin >> n;

    // 保存活动开始时间和结束时间的向量
    vector<pair<int, int>> activities(n);

    // 读取每个活动的开始时间和结束时间
    for (auto& activity : activities) {
        cin >> activity.first >> activity.second;
    }

    // 按活动结束时间对活动进行排序
    sort(activities.begin(), activities.end(), [](const auto& a, const auto& b) { return a.second < b.second; });

    // 保存被选中的活动序号的向量
    vector<int> selected;
    int lastEnd = 0; // 上一个被选择活动的结束时间

    // 遍历排序后的活动列表，选择不冲突的活动
    for (int i = 0; i < n; ++i) {
        // 如果当前活动的开始时间大于等于上一个被选择活动的结束时间，
        // 则说明当前活动与上一个被选择活动不冲突，可以选择
        if (activities[i].first >= lastEnd) {
            selected.push_back(i + 1); // 将符合条件的活动序号加入selected向量
            lastEnd = activities[i].second; // 更新上一个被选择活动的结束时间
        }
    }

    // 输出最大不相交活动集合的大小
    cout << "最大不相交活动集合的大小：" << selected.size() << endl;

    // 输出被选择的活动序号
    cout << "被选择的活动序号：";
    for (auto num : selected) {
        cout << num << " ";
    }

    return 0;
}
                          

运行程序： 将测试用例输入程序。你可以在终端中手动输入活动数量以及每个活动的开始和结束时间，或者将测试用例保存在文本文件中，并使用文件重定向将其输入到程序中。

例如，在终端中手动输入：