去年在集训队带贪心算法的入门课有个新生看到“求可参加最多比赛数”这道题第一反应就是把比赛按开始时间排个序谁开始得早先参加谁。我让他在白板上写了个反例——比赛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 一个“直觉正确”但会翻车的初版策略新手最常见的策略有两种按开始时间排序或者按持续时间排序。这两种都会翻车。按开始时间排序的反例刚才已经说过比赛开始结束A110B23C45按开始时间排序后依次是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_{t1}打架。替换之后最优解依然是合法解数量没有变。这样一来通过不断替换最优解可以逐步变成贪心解而且数量不变这就证明了贪心解至少不差于最优解。听起来有点绕但核心一句话最早结束的那个合法比赛不存在任何理由被排除在最优解之外。2.3 反面教材按开始时间和持续时间的完整对比我把三种排序策略放在一起对比策略反例特征错误原因按开始时间排序一个晚开始但很短的比赛被一个早开始但很长的比赛挡住只考虑开头不考虑后续空间按持续时间排序两场短比赛之间被一场持续时间长但桥接两个短比赛的比赛破坏只考虑单场比赛的“短”不考虑时间区间的位置按结束时间排序无明显反例每步都最大化剩余可用时间贪心选择性质成立这里有一个很重要的判别方法一个贪心策略靠不靠谱别光靠感觉去找反例。如果你能构造出一组数据让策略的选择和正确答案不同那就说明策略错了。按开始时间和按持续时间都能很轻易地构造反例而按结束时间你构造不出来加上上面的交换论证基本可以确定它是对的。3. 手写完整实现从数据读入到结果输出理论说清楚了下面给出完整实现。语言我分别给C和Python这两个足够覆盖绝大多数刷题场景。3.1 数据组织结构体、pair与排序规则C里最简单的做法是用vectorpairint, intpair的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; vectorContest 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(keylambda 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(keylambda 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 now1 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位数字要求删完后剩余数字组成的整数尽可能小。很多人直觉是“每次删最大的那个数字”结果k1时把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。能在第一步选对模型比会写十种高级算法更值钱。最后分享一个我日常工作里的习惯写完贪心代码别急着交先问自己两个问题——第一能不能构造一组数据让这个贪心策略得出错误的答案第二如果能那我该换成什么策略这两个问题想明白才是真的把贪心算法学到手了。那堂课上我把这个习惯教给了新生他后来刷题的正确率肉眼可见地提升了你不妨也试试。