题解 | #活动安排#

首先要想明白能不能用贪心算法：即，每一步都局部最优是否能保证全局最优。我认为这是最重要也是最难理解的。

对于此题，能想到三种局部最优策略：①选最先结束的活动，为后续活动留更多的时间；②选耗时最短的活动，为其它活动留更多时间；③选最先开始的活动，为前面的活动留更多时间。

如下图，■代表活动时间，□代表空闲时间。通过反例可以排序策略②③。

可是找不到排除①的反例并不能说明①就一定对，严格的证明需要用到数学方法。

数学证明我不会，总之记住“活动安排”问题用贪心法就行。

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

struct ActivityTime
{
    int startTime;
    int endTime;
};

int main()
{
    int n;
    std::cin >> n;
    std::vector<ActivityTime> activityTimeList(n); // 活动时间列表
    for (int i = 0; i < n; ++i)
        std::cin >> activityTimeList[i].startTime >> activityTimeList[i].endTime;

    // 先选最早结束的活动
    // 然后选出该活动结束后最早结束的活动
    std::sort(activityTimeList.begin(), activityTimeList.end(),
              [](ActivityTime a, ActivityTime b) {return a.endTime < b.endTime; });

    int cnt = 0;             // 最多可选择的活动数
    int earliestEndTime = 0; // 最早结束时间
    for (const ActivityTime& activityTime : activityTimeList)
    {
        if (earliestEndTime <= activityTime.startTime)
        {
            earliestEndTime = activityTime.endTime;
            ++cnt;
        }
    }
    std::cout << cnt;
}

在某些场景下，穷举求最优解很费时间，可考虑用贪心算法求近似最优解(需要估算误差范围)。

参考资料：

https://leetcode.cn/circle/article/YPuyh