会议室排期、课程时间冲突、兼职岗排班……这些看着互不相干的日常问题，剥掉外表之后其实是同一个算法模型：活动安排问题。它的大意是，给你一批活动，每个活动有开始时间和结束时间，同一时刻只能参加其中一个，要选出数量最多的互不冲突的子集。贪心算法的答案简单到有点反直觉：把所有活动按结束时间排序，然后从头扫一遍，凡是开始时间不早于上一个已选活动结束时间的，就选进来。这句话背下来只要十几秒，但真正写对代码、讲清原理、在业务数据里跑通，中间还隔着不少细节。这篇文章把问题定义、策略辨析、完整实现、正确性证明和工程里的坑通通过一遍，想系统学贪心的、准备算法笔试的、或者被"会议室排期"逼疯的读者，都能找到能直接用的版本。

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, key=lambda x: x[0])，也就是按开始时间排序——这是最容易犯的错。正确写法是key=lambda x: x[1]，按结束时间排。如果希望结束时间相同的活动有稳定的先后顺序，可以用key=lambda x: (x[1], x[0])做复合排序。

3.2 核心实现与手工推演

下面是完整的 Python 实现，不依赖任何第三方库：

def activity_selection(activities): if not activities: return [] # 关键：按结束时间升序排列 act_sorted = sorted(activities, key=lambda 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_end=4。接下来 (3,5) 的开始时间 3 小于 4，冲突，跳过；(0,6) 开始 0 小于 4，跳过；(5,7) 开始 5 不小于 4，选入，last_end=7；之后 (3,8)、(5,9)、(6,10) 都因为开始时间小于 7 被跳过；(8,11) 开始 8 不小于 7，选入，last_end=11；最后 (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, key=lambda 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 selected

3.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_j，gap 代表两个活动之间的最小间隔。

这个坑的隐蔽之处在于，代码看起来一模一样，就是一个等号或者一个加数的事，但线上排班系统要是拿理论版直接上线，会排出"上一秒结束下一秒开始"的班表，业务反馈立刻就来。我在实际项目里处理过类似需求，最终方案是把 gap 作为配置项放进函数：

def activity_selection_with_gap(activities, gap=0): if not activities: return [] ordered = sorted(activities, key=lambda 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

这样测试时 gap=0 是理论版，gap 取具体分钟数就是业务版。

4.2 相同结束时间时，选哪个并不影响数量但影响方案

当一批活动的结束时间相同，排序的稳定性决定了你最终选中的是哪一个。由于它们的结束时间一样，无论先扫描哪个，都不影响"接下来可用的时间点"，所以最终选出的最大数量是一致的。但输出的具体活动集合可能不同。比如业务方有部门优先级，希望同等条件下优先安排市场部的活动，这时候就要在排序键上做文章：key=lambda 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 配置。

第三，需要向别人解释方案时，别只讲步骤，讲交换论证。我见过很多同学习惯快速写代码，但被问"为什么贪心正确"时只会复述"因为要按结束时间排序"。把"替换进最优解"的思路总结成三句话，既能让对方信服，也能帮自己确认真的理解了，而不是背住了结论。

第四，同类的"教室排课""互斥任务选择"问题可以直接套这个框架。把业务里的一切都抽象成"开始时间、结束时间、兼容规则"三件套，然后问自己一句：目标是最多次数还是最大权重？是次数就走贪心，是权重就走动态规划。抽象能力到位之后，这类区间问题基本不会再踩坑。

活动安排问题之所以被反复拿来讲，不是因为题目本身多难，而是因为它把贪心算法的精髓浓缩得干干净净：每次只做局部最优选择，但通过排序和归纳保证全局最优。把这个例子彻底吃透，再遇到任何贪心问题，你至少知道该从哪里开始质疑和验证了。