区间贪心算法详解：区间调度、合并与选点的核心策略与避坑指南

区间贪心问题是我在带新人刷算法题时被问得最多的一类，也是我自己当年栽过跟头的地方。表面上看它只是"排序+遍历"两板斧，但真正上手写的时候，边界条件、排序依据、区间开闭的处理，随便一个细节就能让答案从正确变成"看起来对但过不了"。这篇东西我打算把区间贪心这一类问题彻底拆开讲清楚：它到底在解决什么问题、为什么贪心策略成立、几种典型变体怎么区分、代码怎么写才不容易翻车，以及我在实际调试中踩过的那些坑。不管你是刚接触贪心算法的初学者，还是刷题时总在区间类题目上卡壳的进阶选手，应该都能从里面找到能直接抄作业的东西。核心关键词区间贪心、区间调度、区间合并、区间选点会自然穿插在下面各个部分里，你顺着读下去就行。

1. 区间贪心到底在解决什么问题

1.1 从生活场景理解区间贪心的本质

先说人话。区间贪心处理的是一堆"线段"之间的关系，每条线段有一个起点和一个终点，我们要在这些线段上做某种最优决策。最典型的场景是会议室安排：你手上有一堆会议申请，每个会议有开始时间和结束时间，会议室只有一间，怎么安排能让开成的会议数量最多？这就是经典的区间调度问题。

再比如修路挖坑：市政要在一条马路上分段施工，每段施工有一个区间范围，问最少需要设置多少个施工围挡点，才能覆盖所有施工段？这是区间选点问题。还有像视频剪辑里的时间轴合并、内存块的碎片整理、任务调度系统里的时间片分配，本质上都是区间贪心能套用的模型。

我习惯把区间贪心理解成"在一维数轴上做取舍"。数轴就是那条线，区间就是线上的段，贪心就是每一步都做当前看起来最优的选择，并且相信这个局部最优能导向全局最优。这个"相信"不是拍脑袋，后面会讲为什么在这些特定问题结构下它确实成立。

1.2 区间贪心的三类典型问题划分

实际刷题和工程中遇到的区间贪心，我一般归成三大类，搞清楚分类是选对策略的前提：

这三类的共同点是都要先排序，但排序的依据完全不同，这是最容易搞混的地方。我见过不少人把区间合并的"按左端点排序"直接套到区间调度上，结果样例能过、隐藏用例全挂。所以下面每一类我都会把排序依据为什么这么选讲透。

1.3 为什么贪心在这类问题上成立

很多人对贪心有天然的不信任感，觉得"局部最优不等于全局最优"，这话没错，但区间问题有它特殊的结构。以区间调度为例，假设我们按结束时间从早到晚排序，第一个结束最早的区间一定可以被某个最优解包含——这就是贪心选择性质的体现。直观理解：结束得越早，给后面留的时间就越多，选它不会比选任何其他区间更差。

用交换论证的说法更严谨一点：假设最优解里第一个区间不是结束最早的那个，那我们用结束最早的那个替换它，由于它结束更早，不会和最优解里后续的区间冲突，替换后依然是一个合法解，且数量不变。既然总能替换，那"选结束最早的"就一定是安全的。这个论证思路是理解所有区间贪心正确性的钥匙，后面讲选点问题时还会用到类似逻辑。

注意：贪心成立的前提是问题具备贪心选择性质和最优子结构。区间类问题大多满足，但不是所有"看起来像区间"的问题都能贪心，比如带权区间调度（每个区间有收益，求最大收益）就不能简单贪心，得用动态规划。这个区分后面会专门讲。

2. 三类问题的核心策略与排序依据拆解

2.1 区间调度：为什么必须按右端点排序

区间调度问题的标准解法是：把所有区间按右端点升序排序，然后从头遍历，维护一个"上一个选中区间的结束时间"，如果当前区间的左端点大于等于这个结束时间，就选中它并更新结束时间。

为什么是右端点而不是左端点？我用一个反例说明。假设有三个区间：A=[1,10]，B=[2,3]，C=[4,5]。如果按左端点排序，顺序是A、B、C，先选A，然后B和C都和A重叠，只能选一个，最终答案是1。但正确答案是选B和C，答案是2。按右端点排序则是B、C、A，先选B，再选C（4>=3），A被跳过，答案2，正确。

这个反例的核心在于：左端点小不代表这个区间"占用资源少"，A虽然开始早，但它拖得长，把后面全堵死了。右端点小才意味着"尽早释放资源"。这就是排序依据背后的逻辑——我们要优先选择那些"结束得早、对后续影响小"的区间。

代码实现上，排序用右端点，遍历时判断条件用当前左端点 >= 上次选中右端点。这里有个细节：如果题目允许端点相接（比如会议结束时间和下一个开始时间相同算不冲突），就用>=；如果要求严格不接触，就用>。这个开闭区间的处理是隐藏用例的重灾区，一定要看清题意。

def max_non_overlap(intervals): if not intervals: return 0 # 按右端点升序 intervals.sort(key=lambda x: x[1]) count = 1 last_end = intervals[0][1] for i in range(1, len(intervals)): if intervals[i][0] >= last_end: # 端点相接算不冲突 count += 1 last_end = intervals[i][1] return count

2.2 区间合并：按左端点排序的边遍历边合并

区间合并的目标不一样，它要把所有重叠或相邻的区间揉成尽量少的大区间。策略是按左端点升序排序，然后维护一个当前合并区间的[start, end]，遍历时如果下一个区间的左端点小于等于当前end，说明有重叠，更新end = max(end, 下一个右端点)；否则说明断开了，把当前区间收进结果，重新开始。

为什么这里按左端点排序？因为合并是从左往右推进的，按左端点排序能保证我们处理的区间在数轴上是"有序推进"的，不会出现后面突然冒出一个左端点很小的区间插到前面去。如果按右端点排序，合并逻辑会变得很别扭，因为你无法保证当前维护的区间和下一个区间在位置上连续。

合并时那个max(end, 下一个右端点)很关键。考虑区间 [1,5] 和 [2,3]，后者完全被前者包含，如果不取 max，end 会被错误地更新成 3，把 [1,5] 缩水了。这个细节我在早期写代码时忽略过，导致包含关系的用例全错。

def merge_intervals(intervals): if not intervals: return [] intervals.sort(key=lambda x: x[0]) res = [intervals[0][:]] for start, end in intervals[1:]: if start <= res[-1][1]: # 有重叠或相接 res[-1][1] = max(res[-1][1], end) else: res.append([start, end]) return res

2.3 区间选点：按右端点排序的覆盖逻辑

区间选点问题问的是用最少的点，让每个区间至少包含一个点。经典问法是"射气球"：气球是区间，箭是点，箭沿垂直方向射穿，问最少几支箭。策略是按右端点升序排序，维护上一支箭的位置，如果当前区间的左端点大于箭的位置，说明这支箭没覆盖到它，需要新射一支，位置放在当前区间的右端点。

为什么箭放在右端点？因为放在右端点能最大化覆盖后续区间的可能性——右端点是这个区间最靠右的位置，后续区间只要左端点不超过它就能被覆盖。这和区间调度"选结束最早"是同一个思想的镜像：都是尽量把资源放在"对后续最友好"的位置。

这里同样要注意端点相接的判断。如果气球是闭区间 [1,2] 和 [2,3]，箭射在 2 能同时打穿两个，判断条件用当前左端点 > 箭位置才需要新箭；如果题目定义成开区间，就得用>=。我建议拿到题先把区间开闭在纸上画一下，别凭感觉写。

def min_arrows(points): if not points: return 0 points.sort(key=lambda x: x[1]) arrows = 1 pos = points[0][1] for start, end in points[1:]: if start > pos: # 这支箭覆盖不到 arrows += 1 pos = end return arrows

2.4 三类策略的对照与易混点

把三类放一起对照，能看清它们的内在联系和区别：

最容易混的是调度和选点，两者都按右端点排序，但维护的语义不同：调度维护的是"已选区间的结束时间"，选点维护的是"箭的位置"。写代码时如果变量命名含糊，很容易把逻辑写串。我的习惯是变量名直接体现语义，比如last_selected_end和arrow_pos，别图省事用end一把梭。

3. 完整实操：从读题到代码落地的全流程

3.1 读题阶段的关键信息提取

我做区间题有个固定流程，第一步永远是读题时在纸上标注三件事：区间是开还是闭、端点是整数还是实数、目标是数量最优还是覆盖最优。这三件事决定了后面所有的细节处理。

举个具体例子，题目说"会议结束时间和下一个会议开始时间相同视为不冲突"，那判断就用>=；如果说"时间段不能有任何重叠"，那相同端点也算冲突，用>。再比如端点是实数时，不能用简单的加减一处理相邻，得考虑浮点精度。这些信息在题面里往往藏得很隐蔽，但直接决定对错。

我建议读题时把关键约束抄到代码注释里，比如# 端点相接算不冲突，用 >=，这样写代码时不会写着写着就忘了。这个习惯看着笨，但能省掉大量回头改 bug 的时间。

3.2 排序键的选择与稳定性考量

Python 里排序用key=lambda x: x[1]是最常见的写法，但有些题目会有二级排序需求。比如区间调度里如果两个区间右端点相同，先处理哪个？理论上无所谓，因为右端点相同选哪个都不影响后续，但为了结果稳定，可以加个二级键按左端点排。这种细节在需要输出具体方案（而不只是数量）的题目里就很重要了。

另外要注意，sort是稳定排序，sorted也是，但如果你用key返回元组，比较是按元组字典序来的。我见过有人写key=lambda x: (x[1], x[0])想实现"右端点升序，相同则左端点升序"，这是对的；但如果写成key=lambda x: x[1] - x[0]想按区间长度排，那就完全跑偏了，区间调度根本不看长度。

3.3 边界条件的系统化处理

区间题的边界我总结成一张检查清单，每次写完代码对着过一遍：

• 空输入：intervals为空时返回什么？调度返回 0，合并返回空列表，选点返回 0。
• 单区间：只有一个区间时，调度返回 1，合并返回它本身，选点返回 1。
• 完全包含：一个区间被另一个完全包住时，合并要取 max，调度和选点要正确跳过。
• 端点相接：根据题意决定用>=还是>。
• 全部重叠：所有区间互相重叠时，调度返回 1，合并返回 1 段，选点返回 1。

这张清单我贴在显示器边上过，新人照着过一遍，边界相关的错误能少一大半。尤其是"完全包含"这一条，合并问题里不取 max 的 bug 极其隐蔽，因为大部分用例不会触发，只有特定数据才暴露。

3.4 一个综合案例的完整推演

拿一道综合题练手：给一堆区间，先合并重叠的，再在合并后的区间上求最多能选多少个互不重叠的。这其实是两个子问题的串联。

第一步合并，按左端点排序，边遍历边合并，得到一组互不重叠的区间。第二步调度，由于合并后的区间已经互不重叠，其实直接返回数量就行——但为了演示通用性，还是按右端点排序走一遍调度逻辑。这个案例的价值在于让你体会"合并后的区间天然满足调度前提"这个性质，很多工程场景里就是先做数据清洗（合并）再做决策（调度）。

推演时我会把中间结果打印出来，比如合并前后的区间列表，确认每一步符合预期。调试区间题，打印中间状态比单步跟踪高效得多，因为区间是结构化数据，肉眼扫一遍就能发现异常。

4. 常见翻车点与排查实录

4.1 排序依据选错的典型症状

排序依据选错是区间题第一大坑，症状很有辨识度：样例能过，但提交后部分用例失败，且失败用例往往区间数量较多。原因是小规模数据下不同排序可能碰巧得到相同结果，数据一多就露馅。

排查方法很直接：把失败用例的区间打印出来，手动按两种排序各走一遍，看结果差异。如果按左端点排和按右端点排结果不同，而正确答案对应右端点，那就是排序选错了。我建议平时练习时故意用错误排序跑一遍，观察它错在哪，这种"反向学习"对建立直觉特别有效。

4.2 端点开闭处理不当的隐蔽 bug

端点开闭的 bug 最阴险，因为它只在特定数据上触发。比如调度问题里两个区间 [1,2] 和 [2,3]，用>判断会认为冲突，答案是 1；用>=认为不冲突，答案是 2。如果题目本意是后者而你写了前者，只有这种端点相接的用例会挂。

排查技巧：构造最小反例。拿到一个可疑的端点问题，就造两个端点刚好相接的区间，看代码输出是否符合题意。这个方法比读十遍题面都管用。我现在的习惯是每道区间题都主动构造端点相接的测试用例，作为自测的一部分。

4.3 合并时忘记取 max 的包含陷阱

前面提过，合并时end = max(end, 下一个右端点)里的 max 不能省。忘记取 max 的症状是：包含关系的用例结果错误，被包含的区间会把外层区间的右端点"拉小"。比如 [1,10] 和 [2,3] 合并，错误代码得到 [1,3]，正确是 [1,10]。

这个 bug 的排查靠构造包含用例：造一个长区间套一个短区间，看合并结果是否保持长区间的右端点。我把它列进了合并问题的必测清单，和端点相接并列。

4.4 常见问题速查表

4.5 带权区间：贪心失效的边界

最后必须强调一个贪心失效的场景：带权区间调度。每个区间除了起止还有收益，要求选出一组互不重叠区间使总收益最大。这时候按右端点贪心就错了，因为结束早的区间可能收益极低，选它不如选一个结束晚但收益高的。

反例：区间 A=[1,2] 收益 1，B=[1,3] 收益 100。按右端点先选 A，总收益 1；但最优是选 B，收益 100。这类问题得用动态规划，按右端点排序后对每个区间找前面最后一个不冲突的区间，做状态转移。识别标志就是"有权重/收益"，看到这个关键词就别贪心了。

提示：区间贪心的适用边界是"目标只和区间数量或覆盖关系有关"。一旦引入权重、代价、多目标，先怀疑贪心是否还成立，必要时退回动态规划或整数规划。

5. 我在实战中沉淀的几条经验

5.1 先画图再写码的习惯

我处理任何区间题，第一步都是在纸上画数轴，把样例区间画成线段。这个动作看着原始，但能瞬间暴露重叠关系、包含关系、端点相接这些关键结构。很多 bug 在画图阶段就能预判，比如你画完发现有两个区间完全重合，就会意识到合并时要处理相等情况。

画图还有个好处是方便构造反例。当你怀疑某个策略有问题，直接在图上挪动线段就能造出反例，比在脑子里空想快得多。我带新人的时候，第一课就是让他们画图，画够二十道题，区间直觉自然就有了。

5.2 变量命名即文档

区间题的代码逻辑本身不复杂，复杂的是语义。last_end、arrow_pos、cur_start、cur_end这些名字要能自解释。我见过有人全用a、b、tmp，三天后自己都看不懂。好的命名能让代码读起来像伪代码，review 时一眼就能发现逻辑错位。

具体建议：调度用last_selected_end，选点用arrow_pos，合并用merged_start和merged_end。多打几个字符，换来的是可维护性。

5.3 测试用例的分层构造

我自测区间题会分三层构造用例：第一层是题面样例，确保基本逻辑对；第二层是边界用例，空、单元素、全重叠、端点相接、完全包含各来一个；第三层是随机对拍，写个暴力解法，随机生成小规模区间，比对两者结果。第三层最费事但最有效，很多隐蔽 bug 都是对拍出来的。

暴力解法怎么写？调度就枚举所有子集判断是否互不重叠取最大，选点就枚举点集，规模小的时候完全可行。对拍跑个几百组，基本能覆盖各种边界组合。

5.4 从题目到工程的迁移思考

最后说点题外话。区间贪心不只是刷题用，工程里到处都是它的影子：任务调度系统排时间片、日志系统合并时间窗口、资源分配里找空闲段、甚至前端日历组件渲染重叠事件，底层都是这几套逻辑。我做过一个排班模块，核心就是把员工可用时间段做合并再调度，用的就是本文这套思路。

区别在于工程里要考虑更多现实约束，比如时区、夏令时、精度、并发修改。但算法骨架不变，把区间模型建对，剩下的就是工程细节。所以把这几类问题的策略吃透，收益远超刷题本身。

我个人在实际操作中的体会是，区间贪心的难点从来不在算法本身，而在对问题结构的准确识别和对边界条件的严谨处理。排序键选对、端点开闭看清、包含关系取 max，这三件事做到位，区间题基本不会翻车。剩下的就是多画图、多构造反例、多对拍，把直觉练出来。