贪心典型应用：活动安排问题

活动安排问题：如何用贪心法安排最多的活动？

你一定遇到过这样的场景：周末想约朋友出去玩，可时间总是冲突——上午去游泳，下午要写作业，晚上还有补习班。怎样才能在有限的时间内安排最多的活动呢？这其实就是经典的活动安排问题：给定一系列活动，每个活动有开始时间和结束时间，如何选出互不重叠的活动，使得选出的活动数量最多？

这种问题在现实生活中随处可见：电影院排片（只有一个影厅）、会议室预定、考试时间安排、甚至玩手机游戏时安排不同任务……解决它的巧妙方法叫做贪心算法——每次都选当前看起来“最划算”的那个。

贪心策略：每次选结束最早的活动

想一下：如果你去电影院，经理想安排尽可能多的电影在同一影厅上映。假设有5部电影：

你会怎么排？直觉上，选结束时间最早的电影是最聪明的——因为放完电影后影厅空出来最快，后面就能塞更多电影。按照这个思路，我们先把所有电影按结束时间从小到大排序（结束早的排前面），然后依次检查：如果这部电影的开始时间不早于上一部电影的结束时间，就把它排进去。

为什么这个策略是对的？

有人可能会想：为什么不选开始最早的呢？或者选持续时间最短的呢？我们来举个例子：

• 如果选开始最早的（0点6点），那么整个上午就没了，只能再排一个8点9点的，共2部。
• 但如果选结束最早的呢？排序后结束最早的是[1,4) ？其实不对！仔细看表格，结束最早的电影是哪个？1点4点结束时间4，0点6点结束时间6，5点7点结束时间7，8点9点结束时间9。所以结束最早的是[1,4)。选了它后，下一个可以选[5,7)或[8,9)。这样能选出3部！([1,4)、[5,7)、[8,9) ——共3部，比2部多。

所以按结束时间排序这个贪心策略，每一次选择都为后面留出最多的时间，最终能得到全局最优解。数学上可以证明：只要活动时间不重叠，贪心算法一定找到数量最多的方案。

轻松掌握：一步步教你实现代码

我们用C++来实现这个算法。首先，我们需要一个结构体来存放每个活动的开始和结束时间。然后，按结束时间排序。最后，用循环检查每个活动，只要不冲突就选它。

第一步：定义活动结构

struct Activity {
    int start;  // 开始时间
    int end;    // 结束时间
};

第二步：排序比较函数

我们要按结束时间从小到大排序，所以写一个比较函数：

bool compareEnd(const Activity &a, const Activity &b) {
    return a.end < b.end;  // 结束时间早的排前面
}

注意：< 表示升序，如果写错了（比如写成 a.end > b.end）就会变成降序，结果就错了。

第三步：贪心选择

先设置两个变量：

• count：已选中的活动数量，初始为0。
• lastEndTime：上一个选中活动的结束时间，初始设为 -1（因为时间从0开始，-1表示没有活动）。

然后遍历排序后的活动列表，如果当前活动的开始时间 大于等于 lastEndTime，就选中它，并更新 lastEndTime 为当前活动的结束时间。

int count = 0;          // 已选活动数量
int lastEndTime = -1;   // 上一个活动的结束时间（初始-1便于和0比较）

for (const auto &act : activities) {
    if (act.start >= lastEndTime) { // 不冲突就选
        count++;
        lastEndTime = act.end;
        cout << "选中活动: [" << act.start << ", " << act.end << ")" << endl;
    }
}

完整可运行代码（包含所有细节）

把上面步骤拼起来，加上输入输出，就是完整程序：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Activity {
    int start;  // 开始时间
    int end;    // 结束时间
};

// 比较函数：按结束时间从小到大排序
bool compareEnd(const Activity &a, const Activity &b) {
    return a.end < b.end;
}

int main() {
    // 定义5个活动（每个活动用两个整数表示开始和结束时间）
    vector<Activity> activities = {
        {1, 4},   // 活动1：1点到4点
        {3, 5},   // 活动2：3点到5点
        {0, 6},   // 活动3：0点到6点
        {5, 7},   // 活动4：5点到7点
        {8, 9}    // 活动5：8点到9点
    };

    // 1. 按结束时间排序（升序）
    sort(activities.begin(), activities.end(), compareEnd);

    // 2. 贪心选择
    int count = 0;          // 已选活动数量
    int lastEndTime = -1;   // 上一个活动的结束时间，初始为-1（表示还没有活动）

    for (const auto &act : activities) {
        if (act.start >= lastEndTime) { // 不冲突就选
            count++;
            lastEndTime = act.end;
            cout << "选中活动: [" << act.start << ", " << act.end << ")" << endl;
        }
    }

    cout << "最多可以安排 " << count << " 个活动" << endl;
    return 0;
}

运行后输出：

选中活动: [1, 4)
选中活动: [5, 7)
选中活动: [8, 9)
最多可以安排 3 个活动

咦？你可能会问：代码里选出的是3个活动，但前面举例时说选2个？这是因为前面的例子中我故意没排序直接用了原始顺序。实际上排序后结束最早的是[1,4)，而不是[0,6)。所以最终能选3个！这就是贪心算法的威力。

新手容易犯的3个错误

1. 没有对活动排序：直接按原始顺序判断冲突，结果可能很差。比如上面的例子如果不排序，可能会先选[0,6)，然后[1,4)冲突被跳过，最后只能选[8,9)共2个。而排序后能选3个。

2. 比较函数写反：return a.end > b.end 会按结束时间从大到小排，这样就会先选结束最晚的活动，留出的时间最少，结果不是最优。

3. 忘记更新 lastEndTime：如果只增加count而不更新lastEndTime，后面的活动都会被认为不冲突，导致选了重叠的活动。一定要在选中活动后，把lastEndTime设为当前活动的end。

生活中的更多例子

• 你准备在周末看动画片：有《熊出没》（2:004:00）、《小猪佩奇》（3:004:30）、《汪汪队立大功》（5:006:30）、《超级飞侠》（6:007:00）。按结束时间排序：熊出没（4点）、小猪佩奇（4:30）、汪汪队（6:30）、超级飞侠（7:00）。贪心选：先选熊出没（到4点），然后看下一个开始>=4的：汪汪队5点开始可以选，之后超级飞侠6点开始可以选。最终3部，比不排序强。

• 安排家庭作业：你有4道题，每道题都需要一段连续时间，你想做最多的题目。用同样的方法：按交作业截止时间（结束时间）排序，先做完截止时间早的，这样后面有更多时间。

其他贪心应用和后续学习

贪心算法不只是用于活动安排，它还有很多典型应用：

• 哈夫曼编码：压缩文件时，出现次数多的字符用短编码，每次合并两个出现次数最少的字符。
• 最小生成树：用最少的电线连接所有村庄，每次选最短的线（Kruskal或Prim算法）。
• 任务调度：服务器处理多个任务，每次选耗时最短的，减少等待时间（比如银行柜员处理客户业务）。
• 找零钱问题：用最少的硬币支付指定金额，每次选面值最大的硬币（但要确保面值设计合理）。

掌握了“每次选当前最优”的思想，你可以进一步学习：

• 排序算法：因为贪心通常需要排序，熟练掌握sort函数很有用。
• 结构体与比较函数：自定义类型排序是竞赛中的基本功。
• 动态规划：有些问题贪心不对，要用动态规划（比如找零钱时某些货币组合）。

生活中的很多选择其实也是“贪心”——比如吃饭时先吃自己最爱吃的菜，写作业时先做最简单的题……虽然不一定总是最优，但理解贪心算法能让你更聪明地做决策。试试用代码解决自己身边的活动安排问题吧！