会议室排期、课程时间冲突、兼职岗排班……这些看着互不相干的日常问题剥掉外表之后其实是同一个算法模型活动安排问题。它的大意是给你一批活动每个活动有开始时间和结束时间同一时刻只能参加其中一个要选出数量最多的互不冲突的子集。贪心算法的答案简单到有点反直觉把所有活动按结束时间排序然后从头扫一遍凡是开始时间不早于上一个已选活动结束时间的就选进来。这句话背下来只要十几秒但真正写对代码、讲清原理、在业务数据里跑通中间还隔着不少细节。这篇文章把问题定义、策略辨析、完整实现、正确性证明和工程里的坑通通过一遍想系统学贪心的、准备算法笔试的、或者被会议室排期逼疯的读者都能找到能直接用的版本。1. 先搞清楚问题本身会议室、课程和班表背后的同一个模型1.1 从能挤出几个活动到数学表达假设你是小公司的行政公司只有一个会议室月底收到十几份活动申请每份都写清楚开始时间和结束时间。会议室同一时刻只能装下一个活动你面对的难题是怎样安排能容纳的活动数量最多这不是资源规划问题——公司不缺会议室而是单一资源下的最大兼容子集问题。类似场景遍地都是学校里选课同一时段只能上一门怎么选课才能修到最多门数外卖站点给骑手排班一个骑手同一时间只能跑一单怎么接单能接更多装修师傅排工期一个师傅同一时间只能去一个工地。把它们翻译成数学语言就是下面这套定义给定 n 个活动第 i 个活动用区间 [s_i, f_i) 表示s_i 为开始时间f_i 为结束时间且 s_i f_i。两个活动 i、j 兼容当且仅当 f_i s_j 或者 f_j s_i。要求从这 n 个区间中选出尽可能多的两两兼容的活动。形式化之后很容易发现问题核心就两个词区间、兼容。所有花里胡哨的实现最后都只是在处理区间怎么排序和兼容怎么判断这两件事。1.2 先别急着写代码确认目标函数是什么写任何算法题之前我习惯先确认目标函数。活动安排问题的目标函数是选出的活动数量最大注意是数量不是总时长。这个区别极其关键——它决定了贪心策略的形态。如果目标变成选出的活动总时长最长答案就会变成只挑一个最长区间如果变成收益总和最大贪心也会失效这些变体后面会专门讲。另外还要区分两个容易混的问题。有些场景问的是最少需要几个会议室才能排下所有活动这个问题不叫活动安排问题而是资源数量最小化问题解法走的是另一条路线扫描线计数并发峰值。同一个会议室故事问题问法不同算法完全不同。先把问题类型钉死再谈解法能省下后面很多弯路。2. 三种直觉策略的碰撞为什么只有最早结束站得住脚2.1 最早开始、最短时长、最少冲突为什么都不行很多人包括我当年面对这个问题第一反应是按开始时间排序谁开始得早先安排谁。这个策略有现成的反例一个活动从 8 点到 18 点把所有其他活动都包在它内部按开始时间排序先选了它结果只能安排 1 个而如果跳过它完全可以安排它内部的若干个短活动。同理按持续时间最短优先也有反例一个持续时间很短的活动恰好横跨在两个稍长的活动之间选了它反而把左右两个都挡掉了。再看选冲突数量最少的活动优先这个策略听起来最聪明因为它在做某种全局考量。构造一个例子就能击穿三个互不冲突的小活动共享某个时间段各自又分别和另一个跨多个时段的大活动冲突选出冲突最少的小活动后剩下时间没法再塞进大活动最终数量反而不如放弃它。而且冲突最少需要预先 O(n²) 地计算每个活动和多少其他活动重叠复杂度也不划算。下面这张表把它们摆在一起看结论一目了然策略直观理由反例形态结论按开始时间最早尽早开始利用率高早开始的长区间挡住一堆短区间失败按持续时间最短占用时间少留空间多短区间横跨两个关键边界失败按冲突数量最少最大化自由度三个小活动互斥地分担冲突失败按结束时间最早每次选择给未来留最大余地无正确表格可能看起来有点密但结论值得记牢在最大兼容子集数量这个目标下只有按结束时间排序的贪心策略是正确的。2.2 最早结束的直观逻辑给未来留最多的余量贪心算法讲究局部最优能推出全局最优而最早结束恰好满足这一性质。每一次我们选结束时间最早的活动就相当于把后续安排可用的时间线起点推到了最靠前的位置。这件事可以类比吃自助餐排队你想在一个晚上吃最多家店的招牌菜每家店排队时间各不相同最稳的策略永远是最早能用完餐离开的那家先排因为越早空出时间晚上剩下的时间越多。这种直觉虽然不构成严格证明但对选择算法方向非常有用。反过来按开始时间排序没有任何给未来留余地的保证因为开始早不代表结束早——一个开始最早的活动完全可能结束最晚把后面所有可能性一把堵死。2.3 交换论证一句话说清为什么贪心不会后悔要说服自己或者面试官最早结束永远安全最标准的说法叫交换论证。它的核心思想是任取一个最优解如果它的第一个活动不是全局最早结束的那个那么把它的第一个活动替换成全局最早结束的活动替换后的解依然合法且数量不变。为什么合法因为全局最早结束的活动结束时间不晚于最优解里原第一个活动的结束时间。原第一个活动都能和后面的所有活动兼容说明后面的活动开始时间都不早于原第一个活动的结束时间既然新替换进去的活动结束得更早那它更不可能和后继活动发生冲突。于是存在一个以贪心活动开头的最优解。接下来把问题缩小已经确定的选择不影响剩余子问题而剩余子问题里最早结束的选择同样可以嵌入某个最优解。如此归纳下去贪心每一步都能混进最优解最终贪心解的数量就等于最优解的数量。这个证明看起来有点绕但实际讨论时通常一句话带过每次把贪心选出的活动替换到某个最优解的第一个位置不破坏可行性所以贪心解不小于最优解又因为贪心解本身合法不可能大于最优解因此二者相等。这一句话就是应对你凭什么认为贪心是对的的标准答案。3. 完整代码走读排序、扫描、选入3.1 数据建模与排序键选择工程实现里活动一般就是一条开始时间加结束时间的记录。在 Python 里用元组(start, end)或一个简单类都行。核心数据结构只需要保证扫描时能按结束时间从小到大拿到所有活动同时记得每个活动自己的开始时间。排序键的写法值得提一句。很多人会写成sorted(activities, keylambda x: x[0])也就是按开始时间排序——这是最容易犯的错。正确写法是keylambda x: x[1]按结束时间排。如果希望结束时间相同的活动有稳定的先后顺序可以用keylambda x: (x[1], x[0])做复合排序。3.2 核心实现与手工推演下面是完整的 Python 实现不依赖任何第三方库def activity_selection(activities): if not activities: return [] # 关键按结束时间升序排列 act_sorted sorted(activities, keylambda x: x[1]) selected [act_sorted[0]] last_end act_sorted[0][1] for start, end in act_sorted[1:]: if start last_end: # 与上一个选中的活动兼容 selected.append((start, end)) last_end end return selected if __name__ __main__: acts [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14)] result activity_selection(acts) print(result) # 输出 [(1, 4), (5, 7), (8, 11)]拿这组数据手动走一遍。按结束时间排序后变成(1,4)、(3,5)、(0,6)、(5,7)、(3,8)、(5,9)、(6,10)、(8,11)、(8,12)、(2,14)。初始化选中 (1,4)last_end4。接下来 (3,5) 的开始时间 3 小于 4冲突跳过(0,6) 开始 0 小于 4跳过(5,7) 开始 5 不小于 4选入last_end7之后 (3,8)、(5,9)、(6,10) 都因为开始时间小于 7 被跳过(8,11) 开始 8 不小于 7选入last_end11最后 (8,12)、(2,14) 判断后跳过。最终选中 3 个活动8点到11点这段恰好能塞进 (1,4) 和 (5,7) 之后三条互不重叠结果正确。实际项目中如果还要返回数量直接len(result)即可。如果活动对象属性较多比如带名称、负责人、优先级把元组换成命名元组或者 dataclass 更可读from dataclasses import dataclass dataclass class Activity: name: str start: int end: int def activity_selection_v2(activities): if not activities: return [] ordered sorted(activities, keylambda a: a.end) selected [ordered[0]] last_end ordered[0].end for act in ordered[1:]: if act.start last_end: selected.append(act) last_end act.end return selected3.3 复杂度与变式优化整个算法的成本集中在排序上排序 O(n log n)线性扫描 O(n)总复杂度 O(n log n)。如果不要求输出具体方案只要求最大数量连 selected 列表都不用存只维护计数器空间复杂度可以降到 O(1)。这类只需要数量、少存集合的优化在数据量大时很有意义。还有个常见变式是活动已经按结束时间排好序此时扫描一轮 O(n) 就能出结果。所以有些练习平台会把输入直接描述成已按结束时间升序看到这种描述基本等于送分直接写扫描即可。4. 真实项目里的隐藏坑开闭区间、相等结束时间与输入形态4.1 背靠背是否允许决定你的比较符号理论模型里活动 i 和活动 j 兼容的定义通常是 f_i s_j也就是前一个刚结束、后一个立刻开始是可以的。但在真实业务里背靠背往往不被允许——会议室需要收拾、骑手需要赶路、讲师需要喘口气。此时兼容条件必须改成 f_i gap s_jgap 代表两个活动之间的最小间隔。这个坑的隐蔽之处在于代码看起来一模一样就是一个等号或者一个加数的事但线上排班系统要是拿理论版直接上线会排出上一秒结束下一秒开始的班表业务反馈立刻就来。我在实际项目里处理过类似需求最终方案是把 gap 作为配置项放进函数def activity_selection_with_gap(activities, gap0): if not activities: return [] ordered sorted(activities, keylambda x: x[1]) selected [ordered[0]] last_end ordered[0][1] for start, end in ordered[1:]: if start last_end gap: selected.append((start, end)) last_end end return selected这样测试时 gap0 是理论版gap 取具体分钟数就是业务版。4.2 相同结束时间时选哪个并不影响数量但影响方案当一批活动的结束时间相同排序的稳定性决定了你最终选中的是哪一个。由于它们的结束时间一样无论先扫描哪个都不影响接下来可用的时间点所以最终选出的最大数量是一致的。但输出的具体活动集合可能不同。比如业务方有部门优先级希望同等条件下优先安排市场部的活动这时候就要在排序键上做文章keylambda x: (x.end, x.priority)把优先级作为第二关键字。还有个小细节如果结束时间相同但开始时间更晚某个活动几乎是被别的活动包含的按稳定排序它可能排在前面被优先选中。数量不影响但如果需要输出一个看起来更紧凑的方案可以先按结束时间排再按开始时间升序。总之一句话——只要数量最优具体集合有多种合法答案排序键可以按业务偏好调整不会破坏最优性。4.3 非整型时间、时区与大批量输入的工程处理算法练习里的时间几乎都是整数但真实系统里的时间一般是字符串或者带时区的时间戳。统一转换成整数时间戳再进算法是最省心的做法。直接拿字符串比较在格式统一时碰巧能用但只要出现格式差异就会出错所以别偷懒。大批量输入也要考虑解析方式。我处理过一个百万级活动的场景逐条读取时如果每条都做字符串转换和对象构造会很慢。更好的做法是先用高性能解析一次性转成(start, end)的数组再做排序。内存占用方面Python 默认排序是原地排序额外空间在 O(n) 级别百万数据也没压力。如果数据分布在多个分片里可以先各自排序再归并或者直接全部合入内存按数据规模即可。5. 贪心失效的分支与同类区间问题的分岔口5.1 加权活动安排同一个问题从贪心切换到动态规划活动安排问题最经典的变体是给每个活动加一个权重 w_i目标从数量最多变成总权重最大。贪心在这里立即失效因为数量思维会优先塞进那些权重很小的小活动把高价值的大活动挤掉。反例很容易构造活动 A 从 8 点到 18 点权重 100活动 B、C 都在 A 内部各占一小段权重各 1。按结束时间贪心会先选 B再可能选 C最后总权重 2而直接选 A 能得到 100。这一个例子足够说明数量最优不等于价值最优。加权版本的标准解法是动态规划。先按结束时间排序设 dp[i] 表示前 i 个活动中能获得的最大权重转移方程是 dp[i] max(dp[i-1], dp[p(i)] w_i)其中 p(i) 是结束时间不晚于第 i 个活动开始时间且下标最大的那个活动。求 p(i) 可以用二分因为结束时间是递增的。这个模型在实际业务里很常见比如会议室排期里不同活动有不同的收益权重就不能用本文的贪心做了。5.2 最少会议室问题扫描线才是正解把一个会议室最多安排多少活动换成所有活动都安排下最少要几个会议室问题性质就变了。此时不关心活动之间的挑选关心的是任意时刻最多有几个活动同时进行。答案是同时并发的最大数量用扫描线处理把所有开始事件记为 1结束事件记为 -1按时间轴排序后累加最大值就是要的房间数。也可以用贪心加最小堆模拟按开始时间排序活动每次分配房间时如果最早空闲的房间在活动开始前已释放就复用否则新增一个。这其实是会议室分配的经典题思路和活动安排不完全一样但同样非常实用。5.3 和区间合并、区间覆盖相对照区间类问题经常放在一起考三者的目标和贪心策略完全不同问题目标核心策略活动安排/最大不重叠区间选出的互不重叠区间数量最多按结束时间排序能选就选区间合并把重叠的区间合并成不相交的大区间按开始时间排序合并相邻区间覆盖用最少区间覆盖目标范围按开始时间排序每次都选能延伸最远的我见过不少人在区间覆盖问题上套按结束时间排序的解法结果一测就挂。先想清楚目标再选排序键和贪心策略比背模板可靠得多。6. 把代码写进项目前我的几条实操体会文章最后不写什么总结了直接分享几条我在实际写这类算法时的体会都是吃过亏之后记住的。第一写任何贪心题先回答两个问题目标函数是什么排序键是什么活动安排的目标函数是数量排序键是结束时间。这两个问题想清楚了代码基本是顺水推舟想不清楚百分之八十会写成按开始时间排序的错版本。第二测试用例要覆盖极端形态。空列表、只有一个活动、所有活动互相重叠、所有活动完全不重叠、两个活动背靠背这五类用例五分钟就能写完但能拦住绝大多数回归问题。尤其是背靠背用例专门用来验证你是不是漏了 gap 配置。第三需要向别人解释方案时别只讲步骤讲交换论证。我见过很多同学习惯快速写代码但被问为什么贪心正确时只会复述因为要按结束时间排序。把替换进最优解的思路总结成三句话既能让对方信服也能帮自己确认真的理解了而不是背住了结论。第四同类的教室排课互斥任务选择问题可以直接套这个框架。把业务里的一切都抽象成开始时间、结束时间、兼容规则三件套然后问自己一句目标是最多次数还是最大权重是次数就走贪心是权重就走动态规划。抽象能力到位之后这类区间问题基本不会再踩坑。活动安排问题之所以被反复拿来讲不是因为题目本身多难而是因为它把贪心算法的精髓浓缩得干干净净每次只做局部最优选择但通过排序和归纳保证全局最优。把这个例子彻底吃透再遇到任何贪心问题你至少知道该从哪里开始质疑和验证了。