企业官网建设流程全解析

去年在集训队带贪心算法的入门课，有个新生看到“求可参加最多比赛数”这道题，第一反应就是：把比赛按开始时间排个序，谁开始得早先参加谁。我让他在白板上写了个反例——比赛A是[1, 10]，比赛B是[2, 3]，比赛C是[4, 5]，他写完自己愣住了。按开始时间选，先选A，整条时间轴被锁死，最后只能看一场；但正确答案是先看B和C，能看两场。

这个题目在刷题平台上的出镜率极高，也是贪心算法最适合入门的模型之一。它本质上是经典的区间调度问题：给定若干带开始时间和结束时间的比赛，选出尽可能多的互不重叠的比赛。这篇文章从模型建立讲到贪心策略的正确性论证，再给完整可复现的C++和Python实现，最后把边界条件和常见变体一并说清。适合算法初学者、准备面试的开发者，也适合想搞明白“为什么这个贪心是对的”的人。

1. 先把题目翻译成模型：从“能参加几场”到区间调度问题

很多同学上来就写代码，结果连题都没读完，这题其实非常需要建模这一步。你面对的是赛事表，每场比赛有固定的开始时间和结束时间，一天内的时间轴就是一条线段，每场比赛就是线段上的一个子区间。你要从这堆线段里挑出尽量多条，互不覆盖。

1.1 为什么“比赛”只是一个壳

这个题的通用叫法是活动选择问题（Activity Selection Problem）。把“比赛”换成“会议”“课程”“面试”“任务”，方法完全一样。我面试候选人时最爱用的版本是：一天有n场面试，每场有开始和结束时间，你能参加多少场。本质上就是同一道题。

参赛规则有两条：

• 同一时刻只能参加一场比赛，所以任意两场被选中的比赛不能有重叠时间；
• 如果两场比赛的结束和开始刚好接上，比如第一场[1, 2]结束，第二场[2, 3]开始，通常视为可以连续参加。具体要看题面有没有额外说明。

形式化描述是这样：输入n，然后给n行，每行两个整数s和e，表示第i场比赛的开始时间和结束时间。输出一个整数，表示最多能参加的比赛数量。

1.2 暴力枚举为什么不可行

最朴素的想法是枚举所有子集，检查每个子集内部是否互不重叠，取最大的合法子集大小。这个方法在n很小的时候是能跑的，但是一旦n到20以上，2的n次方个子集会直接爆炸。n取50就已经是天文数字，n到1000、10000的时候，暴力完全没有任何生存空间。

这就逼着你找更聪明的策略。动态规划可以做，但要O(n²)甚至更复杂。而贪心的价值在于：排序只需要O(n log n)，扫描只需要O(n)，整体复杂度极低。但贪心的前提是必须证明局部最优确实能推出全局最优，否则就是瞎蒙。

1.3 一个“直觉正确”但会翻车的初版策略

新手最常见的策略有两种：按开始时间排序，或者按持续时间排序。这两种都会翻车。

按开始时间排序的反例刚才已经说过：

按开始时间排序后依次是A、B、C，贪心选A，结束时间是10，后面的B和C全都冲突，只能参加1场。正确答案选B和C，共2场。问题出在：早开始的比赛可能会霸占很长的时间段，毁了后面所有可能性。

按持续时间排序看似也有道理：挑最短的，不就能塞更多吗？但同样有反例。三场比赛：[1, 100]持续99小时，[101, 102]持续1小时，[103, 104]持续1小时，答案显然是2；但再加上一场[99, 105]持续6小时，按持续时间排序会先选两场1小时的，然后结束。这些反例共同指向一个结论：你选的每一场比赛，都不应该给别人制造障碍，而最不障碍别人的比赛，是结束时间最早的。

2. 贪心核心：为什么按结束时间排序是最优的

先说结论：把所有比赛按结束时间从早到晚排序，然后从前往后扫描，只要当前比赛的开始时间不早于上一场已选比赛的结束时间，就选择它。这个策略每次都是选“当前结束时间最早且不冲突”的比赛。

2.1 直观解释：给后来者留足剩余时间

用一个生活类比。你在一个场馆里安排活动，场地租到很晚都行。现在有人报上来一堆活动，有的上午9点开始晚上9点结束，你选了它，整天就没了；有的上午10点到11点，还有的下午3点到4点。只要脑子没坏，都会先排那个11点就结束的，因为这样下午还能塞别的事。

把“场馆”换成你的个人时间轴，道理完全一样。每次选择结束时间最早的合法比赛，等于把剩下的时间轴尽量完整地留给后面的比赛。每次做这个局部最优选择，都不会破坏全局的可行性，反而会让后续的可用时间尽可能长。

2.2 严谨一点的说明：交换论证思路

如果你只是在刷题，背结论就够了；但如果你面试被问到“你能证明一下吗”，就需要懂一点交换论证（exchange argument）。

设贪心算法选出的比赛序列是a1, a2, ..., ak，某个最优解的比赛序列是o1, o2, ..., om。现在比较这两个序列，找到第一个不一致的位置t。也就是说，前面t-1个完全一样，从第t个开始，贪心选了a_t，最优解选了o_t，而且a_t在排序中排在o_t前面，所以a_t的结束时间一定不晚于o_t的结束时间。

关键是：把最优解里的o_t替换成a_t，不会产生新的冲突。因为a_t的开始时间必然不早于上一场o_{t-1}的结束时间，而a_t的结束时间又不晚于o_t的结束时间，所以它也不会和o_{t+1}打架。替换之后，最优解依然是合法解，数量没有变。这样一来，通过不断替换，最优解可以逐步变成贪心解，而且数量不变，这就证明了贪心解至少不差于最优解。

听起来有点绕，但核心一句话：最早结束的那个合法比赛，不存在任何理由被排除在最优解之外。

2.3 反面教材：按开始时间和持续时间的完整对比

我把三种排序策略放在一起对比：

这里有一个很重要的判别方法：一个贪心策略靠不靠谱，别光靠感觉，去找反例。如果你能构造出一组数据，让策略的选择和正确答案不同，那就说明策略错了。按开始时间和按持续时间都能很轻易地构造反例，而按结束时间你构造不出来，加上上面的交换论证，基本可以确定它是对的。

3. 手写完整实现：从数据读入到结果输出

理论说清楚了，下面给出完整实现。语言我分别给C++和Python，这两个足够覆盖绝大多数刷题场景。

3.1 数据组织：结构体、pair与排序规则

C++里最简单的做法是用vector<pair<int, int>>，pair的first存开始时间，second存结束时间。排序时注意，默认的sort按first排，不是按结束时间排，所以要自定义lambda。

我个人的习惯是定义一个小结构体，可读性更好，尤其是后续如果比赛还要带积分，结构体天然能扩展：

#include <bits/stdc++.h> using namespace std; struct Contest { int start, end; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<Contest> contests(n); for (int i = 0; i < n; i++) { cin >> contests[i].start >> contests[i].end; } sort(contests.begin(), contests.end(), [](const Contest& a, const Contest& b) { if (a.end != b.end) return a.end < b.end; return a.start < b.start; }); int lastEnd = -1; int ans = 0; for (const Contest& c : contests) { if (c.start >= lastEnd) { ans++; lastEnd = c.end; } } cout << ans << "\n"; return 0; }

这里排序比较器我写了两层：第一层按结束时间升序，第二层按开始时间升序。第二层其实不影响答案，但让排序结果可预期，对拍调试时更容易人肉追踪。

3.2 Python版本

Python的写法更简洁，用tuple加lambda就行：

import sys def main(): data = sys.stdin.read().strip().split() if not data: return n = int(data[0]) contests = [] idx = 1 for _ in range(n): s = int(data[idx]) e = int(data[idx + 1]) idx += 2 contests.append((s, e)) contests.sort(key=lambda x: (x[1], x[0])) last_end = -1 ans = 0 for s, e in contests: if s >= last_end: ans += 1 last_end = e print(ans) if __name__ == "__main__": main()

Python里sort(key=lambda x: (x[1], x[0]))天然先按结束时间再按开始时间排序，代码少很多。如果你的输入量非常大，建议用sys.stdin.buffer.read()而不是input()，能省下大量I/O时间。

3.3 核心扫描逻辑到底在做什么

扫描部分一共就三行逻辑，但值得仔细讲清楚。

lastEnd记录的是当前已经选择的最后一场比赛的结束时间，你也可以叫它“当前时间线推进到的位置”。遍历排序后的比赛时，如果当前比赛c.start >= lastEnd，说明它和已经选好的所有比赛都不冲突，可以参加，于是答案加一，同时把lastEnd更新为c.end。如果c.start < lastEnd，说明它和上一场选中的比赛有时间重叠，直接跳过。

注意那个>=。如果题目允许“上一场刚结束，下一秒就进下一场”，就用>=；如果题目要求两场比赛之间必须至少有一段间隔，就改成>。我见过太多人在这里凭感觉写，最后WA得一头雾水。边界符号必须钻到题面里去抠。

3.4 复杂度分析与运行时间

时间复杂度：排序O(n log n)，扫描O(n)，整体就是O(n log n)。n从1到10万，这个复杂度都毫无压力。空间复杂度是O(n)，主要花在存储比赛列表上，如果只求答案不需要保存全部比赛，也可以边读边处理，但排序决定了你还是要存下来。

如果要追求极致性能，结束时间的取值范围如果有限，还可以用桶排序把排序部分优化到O(n)，但绝大多数题目没这个必要。我在带训练时总对学生说：先写对，再考虑优化；先证明贪心正确，再谈性能。

4. 真正拉开水平差距的边界条件和隐藏细节

这一节才是重点。很多人看了上面的代码觉得自己会了，结果一提交就WA。以下每一个坑都是我实际见过至少一次的问题。

4.1 第一个坑：lastEnd的初始值到底是多少

我见过有人把lastEnd初始化成0，然后第一场比赛[0, 1]就正常选了，看起来没问题。但如果比赛时间允许是负数呢？如果所有比赛的开始时间都大于0，初始化为0其实也能跑，但一旦第一场比赛的开始时间就是0，判断c.start >= lastEnd，也就是0 >= 0，成立，没问题。

真正的风险出现在另一种写法里：如果你用的是c.start > lastEnd，并且初始化为0，那么第一场比赛[0, 1]会被错误地跳过。最稳妥的做法是把lastEnd初始化成一个比所有可能开始时间都小的值，比如-1，或者INT_MIN。这样无论比赛从0开始还是从-1000开始，第一场合法比赛永远不会被误杀。

4.2 第二个坑：结束时间相同怎么办

结束时间相同的情况下，比如[1, 5]和[2, 5]，你选哪个都只能选一个，因为两场都在5点结束，互相重叠，不可能都参加。所以排序的第二关键字真的不影响答案。

但比较器本身要注意：C++的lambda必须满足严格弱序，也就是说相等时不能返回true。有人图省事写return a.end <= b.end，这在某些标准库实现里会导致未定义行为，排序结果不可预期甚至直接崩。正确的写法是a.end != b.end ? a.end < b.end : a.start < b.start。

4.3 第三个坑：区间完全包含时为什么自动规避

看这组数据：

3 1 10 2 3 4 5

按开始时间排序贪心会选[1, 10]，然后只能看1场。但按结束时间排序，[2, 3]最先结束，选它；接着[4, 5]开始时间4 >= 3，选它；最后[1, 10]开始时间1 < 3，跳过。答案是2。

这个案例想说明的是：当一个长区间包含一个短区间时，贪心算法天然会选短区间，因为短区间结束早。而一个常见的错误做法是“如果长区间价值更大就优先长区间”——在“最多数量”的题面下，这是错的，因为长区间会挤掉数量优势。只有到加权版本（每个比赛带积分）时，这个判断才需要重新考虑，后面第5节会展开。

4.4 一次典型WA的完整排查链路

前阵子集训队有个学生交了这么一版代码：

sort(contests.begin(), contests.end(), cmp); int now = 0, cnt = 0; for (auto c : contests) if (c.start > now) { cnt++; now = c.end; }

样例全过，提交WA。我让他按这个流程排查：

第一步，怀疑排序。先单独跑排序后的数组，肉眼检查结束时间是否有序，结果没问题。

第二步，怀疑初始值。把now从0改成-1，重新跑样例，还是WA。

第三步，专门构造“无缝衔接”的样例：

3 1 2 2 3 3 4

正确结果是3。他的代码输出1。原因出在c.start > now，1 > 0成立，选第一场，now变成2；第二场2 > 2不成立，跳过；第三场3 > 2成立，选第三场，答案2。等等，这里答案是2，不是1——假设第一场是从[0,1]开始的数据，则会全部跳过。

实际上能直接暴露问题的用例是：

2 0 1 1 2

正确结果2，他的代码输出1，因为第二场1 > 1不成立。问题就锁定在判断条件上。题目语义是“第1场结束后可以立刻开始第2场”，那这里就该用>=。

第四步，修复后，我又让他写一个暴力枚举函数，对拍上千组随机小数据，确认修复后的贪心答案和暴力答案在全部随机用例上一致。这一步非常推荐作为刷题习惯：别等评测机告诉你错，自己先拿暴力对拍。

4.5 大输入时的I/O性能

C++如果cin不加ios::sync_with_stdio(false)和cin.tie(nullptr)，在n达到10万甚至100万时，几百毫秒的I/O开销是实打实的。Python则优先用sys.stdin.buffer.read()整块读入，而不是反复调用input()。算法部分再快，I/O卡脖子一样超时，这个细节竞技选手都懂，但新人经常忽略。

5. 同源贪心题的串讲：删数问题与更复杂的变体

讲完比赛问题，必须提一嘴同为贪心经典题的删数问题，因为这两个放在一起看，你对“贪心的局部最优到底指什么”会有更深理解。

5.1 删数问题：为什么每次删最大数是错的

删数问题长这样：给一个数字字符串，比如10200，允许删掉k位数字，要求删完后剩余数字组成的整数尽可能小。很多人直觉是“每次删最大的那个数字”，结果k=1时，把2删掉得到1000，但其实把第一位1删掉得到0200，也就是200，比1000小多了。

问题出在哪？因为数字的高位权重远大于低位。你真正该删的不是“数值最大的位”，而是从高位往低位看，第一个比后一位大的数字，因为这一位维持了高位的“大”，把它删掉，后一位的较小数字能往上顶一位，数值立刻变小。局部最优是“消除第一个逆序对”，不是“删最大数字”。

5.2 删数问题的高效实现：单调栈思路

高效做法是用一个单调递增栈。遍历数字串，维护栈内元素单调不减，如果当前数字比栈顶小，且还有删除次数，就把栈顶弹出去，相当于删掉一个“高位大数”，然后把当前数字压入栈。遍历结束后如果还剩删除次数，就从末尾连续删。

这个做法的局部最优和“按结束时间排序”的贪心非常像：每走一步都消除当前最影响全局质量的局部逆序。两个题在证明上也都依赖交换论证。所以我会把这两个题放在同一个训练单元里教，学生理解起来特别快。

5.3 加权区间调度：贪心失效的临界点

学完“最多比赛数”，紧接着就该知道它的升级版：每个比赛现在带一个积分value[i]，要求的是能获得的最大总积分，而不是最多场次。

这时“按结束时间排序，能选就选”的贪心直接失效。原因很简单：一场积分为100但时间很长的比赛，可能远远好过三场积分为1的短比赛。最优解的目标从“数量”换成了“加权和”，就不再天然偏向数量多的方案。正确解法是动态规划：按结束时间排序后，dp[i]表示前i场比赛中能获得的最大积分，转移时要么不选第i场，要么选第i场并加上第i场的积分和它前面最近的不冲突比赛的dp值。复杂度O(n log n)用二分查最近不冲突的前驱，或者O(n²)朴素做法。

这个对比特别有价值。它说明一个关键点：贪心之所以是贪心，是因为题目结构恰好保证了“局部最优就是全局最优”；一旦目标函数变了，这个保证随时会崩塌。赛场上最忌讳的就是把某个贪心策略死记硬背，套到所有题上。

5.4 这套思路在真实工程里的应用

出了刷题平台，这个模型也大量出现在工程里。会议室系统一次只能开一个会，要尽量排满当天场次；工程师一天有多个候选任务，每个任务有时间窗，想尽量完成数量；广告系统要在一个时间段里安排尽量多个不冲突的广告位。这些本质上都是“区间不重叠最大化数量”的贪心。

我自己的习惯是，接到这种需求先不急着上动态规划。先问一句：目标函数是不是“尽量多的数量”？如果答案是“是”，而且单位时间价值差不多，那贪心很可能就是最优解，O(n log n)就能搞定。如果带了权重和优先级，再退一步考虑DP。能在第一步选对模型，比会写十种高级算法更值钱。

最后分享一个我日常工作里的习惯：写完贪心代码，别急着交，先问自己两个问题——第一，能不能构造一组数据让这个贪心策略得出错误的答案？第二，如果能，那我该换成什么策略？这两个问题想明白，才是真的把贪心算法学到手了。那堂课上，我把这个习惯教给了新生，他后来刷题的正确率肉眼可见地提升了，你不妨也试试。