企业官网建设流程全解析

前言

活动安排问题（activity selection problem）是贪心算法最标准的入门例子：有一组活动，每个活动有开始时间与结束时间，同一时刻只能进行一个活动，求最多能安排多少个互不重叠的活动。它的贪心策略非常简洁——按结束时间从早到晚排序，依次选择与已选活动不冲突的那个。

常见误解有三个。第一，按开始时间排序。直觉上「先开始的先安排」似乎合理，但它会选出很短视的解：一个从 0 点开始、持续到 23 点的活动会挤掉后面所有活动。第二，认为「每次选持续时间最短的」也可以。这个策略在部分输入上能过，但不是普遍最优，反例很容易构造。第三，把活动安排问题与「带权活动安排」混为一谈。后者每个活动有收益，目标是总收益最大，贪心不再成立，必须用动态规划。

本文给出贪心策略的正确性论证思路、完整实现与边界处理，并说明它什么时候会失效。示例以 C++17 为基准。

一、贪心选择性质：为什么选最早结束的

贪心算法要正确，需要满足两个条件：贪心选择性质（greedy-choice property）与最优子结构（optimal substructure）。活动安排问题两者都满足。

贪心选择性质的论证用交换论证（exchange argument）。设所有活动按结束时间排序，第一个结束的活动是 a₁。任取一个最优解 S，设它的第一个活动是 b。如果 b 就是 a₁，结论成立；否则，把 b 替换成 a₁：因为 a₁ 的结束时间不晚于 b，替换后 a₁ 不会与 S 中后续任何活动冲突（后续活动的开始时间都不早于 b 的结束时间，而 a₁ 结束得更早）。替换后解的大小不变，仍是最优解。因此存在一个包含 a₁ 的最优解，贪心地选它不会错过最优。

最优子结构：选了 a₁ 之后，剩余可选活动的集合是「开始时间不早于 a₁ 结束时间」的那些，原问题的最优解去掉 a₁ 后，正好是这个子问题的最优解。否则把子问题更优的解接上 a₁，会得到比原最优解更大的解，矛盾。

这两条合起来，说明「按结束时间排序后依次贪心」得到的解是最优的。注意论证里用的是「结束时间不晚于」，不是「持续时间最短」——后者无法保证替换后不冲突。

二、排序与选择

实现分两步：先按结束时间升序排序（结束时间相同则按开始时间升序，保证确定性），再线性扫描，维护「上一个被选活动的结束时间」。对每个活动，如果它的开始时间不早于上一个结束时间，就选中它并更新结束时间。

判断冲突时要比较上一个被选中活动的结束时间，而不是排序后第一个活动的结束时间，因此需要一个独立变量记录它。第一个活动没有「上一个」，用一个布尔标志区分，比给结束时间设一个「足够小」的哨兵更稳妥。

// 适用于 C++17
#include <algorithm>
#include <vector>

struct Activity {
int start;
int finish;
int id;
};

std::vector<int> select_activities(std::vector<Activity> acts) {
std::sort(acts.begin(), acts.end(),
[](const Activity& a, const Activity& b) {
if (a.finish != b.finish) {
return a.finish < b.finish;
}
return a.start < b.start;
});

std::vector<int> chosen;
bool has_last = false;
int last_finish = 0;

for (const Activity& a : acts) {
if (!has_last || a.start >= last_finish) {
chosen.push_back(a.id);
last_finish = a.finish;
has_last = true;
}
}
return chosen;
}

用has_last而不是给last_finish设一个「足够小」的哨兵，是为了避免时间可能是负数时的边界问题。哨兵写成INT_MIN看似可行，但如果活动的开始时间也允许取INT_MIN，比较仍然成立；真正的风险在于有人把哨兵写成 0，而活动时间允许为负，第一个活动就会被错误跳过。布尔标志没有这个问题。

a.start >= last_finish的语义是「上一个活动结束的瞬间，下一个活动可以开始」，即端点相接不算冲突。如果业务要求两个活动之间必须有间隔（例如清理时间），把>=改成>即可，但要在接口文档里写清楚。

函数按值接收std::vector<Activity>，排序的是副本，调用者的原数组不受影响。如果活动数量很大、复制成本高，可以改成const&接收并在函数内部复制一份，或者让调用者明确知道「这个函数会重排传入的容器」。不要在参数上写std::vector<Activity>&又在函数里排序，那会悄悄修改调用者的数据。

三、完整示例

下面用一组经典数据演示。活动以「开始、结束」表示，编号从 1 开始。

// 适用于 C++17
#include <algorithm>
#include <iostream>
#include <vector>

struct Activity {
int start;
int finish;
int id;
};

std::vector<int> select_activities(std::vector<Activity> acts) {
std::sort(acts.begin(), acts.end(),
[](const Activity& a, const Activity& b) {
if (a.finish != b.finish) return a.finish < b.finish;
return a.start < b.start;
});

std::vector<int> chosen;
bool has_last = false;
int last_finish = 0;
for (const Activity& a : acts) {
if (!has_last || a.start >= last_finish) {
chosen.push_back(a.id);
last_finish = a.finish;
has_last = true;
}
}
return chosen;
}

int main() {
std::vector<Activity> acts = {
{1, 4, 1}, {3, 5, 2}, {0, 6, 3}, {5, 7, 4},
{3, 9, 5}, {5, 9, 6}, {6, 10, 7}, {8, 11, 8},
{8, 12, 9}, {2, 14, 10}, {12, 16, 11}
};

const std::vector<int> chosen = select_activities(acts);
std::cout << "count: " << chosen.size() << '\n';
for (int id : chosen) {
std::cout << id << ' ';
}
std::cout << '\n';
return 0;
}

按结束时间排序后，依次考察：活动 1（1 到 4）最先结束，选中；活动 2（3 到 5）开始于 3，早于 4，跳过；活动 3（0 到 6）同样跳过；活动 4（5 到 7）开始于 5，不早于 4，选中；活动 5、6 的开始时间都早于 7，跳过；活动 7（6 到 10）早于 7，跳过；活动 8（8 到 11）不早于 7，选中；活动 9（8 到 12）开始于 8，早于 11，跳过；活动 10（2 到 14）跳过；活动 11（12 到 16）不早于 11，选中。最终选中 1、4、8、11，共四个活动，时间轴为 1–4、5–7、8–11、12–16。

这组数据的最优解确实是 4 个。可以手工验证：任何五个互不重叠的活动，总时长至少覆盖 1 到 16 的某个区间，而按上面的划分已经没有插入空间。

四、复杂度与失效场景

贪心在此题成立的关键是「目标函数是活动个数」，每个活动的价值相同。一旦每个活动带有不同收益，问题变成带权活动安排（weighted interval scheduling），贪心立刻失效。反例：活动 A 为 0 到 10、收益 100，活动 B 为 0 到 5、收益 1，活动 C 为 6 到 10、收益 1。按结束时间贪心会选 B 和 C，总收益 2；最优解是只选 A，收益 100。

带权版本要用动态规划：按结束时间排序后，对每个活动 i 计算p(i)（在 i 开始前结束的最后一个活动的下标），然后dp[i] = max(dp[i-1], profit[i] + dp[p(i)])。这个转移的正确性依赖「活动要么选、要么不选」的二选一结构，复杂度 O(n log n)（排序加二分查找 p(i)）。

此外，活动安排问题假设「同一时刻只能做一个活动、活动不可拆分、时间区间是闭区间」。如果允许多资源并行，问题变成区间图着色，贪心要按开始时间排序并维护资源池；如果活动可拆分，问题退化成「总时长除以资源数」的装箱类问题。题目的假设变了，算法也要跟着变。

常见坑点

坑点一：按开始时间排序。

❌std::sort(acts.begin(), acts.end(), [](auto& a, auto& b) { return a.start < b.start; });，可能选到一个超长活动，挤掉后面全部。

✅ 按结束时间升序排序。

坑点二：比较的是排序后第一个活动的结束时间。

❌ 用acts[0].finish作为「上一个结束时间」，扫描过程中从不更新。

✅ 用独立变量last_finish，每选中一个活动就更新。

坑点三：端点相接被误判为冲突。

❌ 用a.start > last_finish做严格比较，本来可以相接的活动被跳过。

✅ 默认语义是闭区间相接可接受，用a.start >= last_finish；需要间隔时再改。

坑点四：把带权版本也套贪心。

❌ 每个活动有收益时仍按结束时间贪心，得到次优解。

✅ 带权活动安排用动态规划，按dp[i] = max(dp[i-1], profit[i] + dp[p(i)])转移。

坑点五：函数内排序修改了调用者的数据。

❌ 参数写成std::vector<Activity>&并在函数里sort，调用方的顺序被改变。

✅ 按值接收副本，或明确文档说明会重排。

坑点六：用 0 作为结束时间的哨兵。

❌int last_finish = 0;且允许负时间，第一个开始时间为负的活动被跳过。

✅ 用has_last标志，或在排序后直接选第一个活动作为初始状态。

坑点七：忽略start > finish的非法输入。

❌ 数据里混入开始晚于结束的活动，排序与选择结果不可解释。

✅ 入口校验，非法活动过滤或抛异常。

坑点八：结束时间相同时排序不稳定导致结果不确定。

❌ 只比较finish，相同结束时间的活动顺序由实现决定。

✅ 补充start作为次级比较键，保证输出确定。

总结

活动安排问题之所以适合作为贪心的第一课，是因为它的正确性可以用一段简短的交换论证讲清楚，而代码只有排序加一次扫描。但它也提醒我们：贪心不是「看起来合理」就成立，它需要证明。把「按结束时间」换成「按开始时间」或「按持续时间」，代码只改一行，正确性却完全不同。判断一个贪心策略能不能用，先试着构造反例；构造不出来，再去找交换论证。