区间贪心是算法面试里出镜率极高的一类题，但真正让人头疼的不是"知道要用贪心"，而是"面对一道新题，怎么在十分钟内判断它到底能不能贪、该按什么维度贪"。我见过太多人背了一堆模板，考场上换个马甲就懵了。这篇内容就是把我这些年刷题、带人、复盘踩坑的经验揉在一起，从"为什么贪心能成立"讲到"具体怎么落地"，再到"哪些地方最容易翻车"，适合刚接触贪心、想系统梳理一遍的读者，也适合已经会写但总在边界条件上栽跟头的老手。区间贪心本质上是"在一条数轴上做取舍"的学问，核心关键词就三个：区间、排序维度、贪心选择。把这三件事想透，绝大多数变种题都能拆开看。

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

1.1 从"会议室安排"说起：贪心的现实原型

区间贪心最经典的原型是会议室安排：给你一堆会议的开始和结束时间，问一间会议室最多能排几场。这个问题之所以经典，是因为它把"取舍"这件事具象化了——每个会议都占一段时间，时间不能重叠，你要在有限资源下塞进尽可能多的会议。

我第一次接触这类题时，本能反应是"按开始时间排，然后一个个试"。结果很快发现不对：一个从早上八点开到晚上八点的长会，会把后面所有短会全挤掉。正确的直觉应该是"优先选结束早的"，因为结束越早，留给后面的时间越多。这个"结束早优先"就是区间贪心最核心的一条经验法则，后面所有变种几乎都是它的变形或组合。

理解这个原型很重要，因为区间贪心的所有题目，本质上都是在问同一个问题：在一条一维数轴上，给定若干带权或不带权的线段，如何做出局部最优选择，使得全局结果最优。会议室是"数量最多"，还有的是"覆盖最全""重叠最少""删除最少"等等，但底层结构完全一致。

1.2 贪心与动态规划的分水岭在哪

很多人分不清区间题什么时候用贪心、什么时候用 DP。我的判断标准很直接：看"选择当前区间"会不会影响"后面区间的可行性判断"。如果选了一个区间之后，剩下的问题结构和原问题完全一样、只是规模变小，而且当前选择不会让后面变差，那大概率能贪。如果选完之后还要"回头反悔"或者"记录多种状态"，那就是 DP 的活。

举个具体对比：会议室安排（最多不重叠区间数）能贪，因为选了结束最早的，剩下的时间轴是连续的、独立的。但"带权区间调度"（每个会议有价值，求总价值最大）就不能简单贪了——结束早的会议可能价值极低，选它反而亏。这时候就得用 DP，按结束时间排序后做状态转移。

提示：判断能不能贪，先问自己"我能不能构造一个反例，让局部最优导致全局变差"。构造不出来，再尝试证明交换论证；构造得出来，立刻转 DP。

1.3 三类最常见的区间模型

刷多了会发现，区间贪心的题目基本落在三个模型里，认清模型比背代码有用得多。

这三类模型覆盖了八成以上的区间贪心题。拿到新题先归类，归到哪类就往对应的排序维度和策略上套，比从零推导快得多。当然也有混合模型，比如"用最少区间覆盖目标段"同时又要"区间不重叠"，那就得把两个模型的策略叠起来用，这个后面会专门讲。

2. 排序维度选错，后面全白搭

2.1 为什么"按左端点排"是个高频陷阱

新手最容易犯的错，就是无脑按左端点排序。因为大部分区间题输入就是按左端点给的，或者直觉上"从左往右处理"很自然。但排序维度选错，贪心策略再对也没用。

拿会议室安排举例：如果按左端点升序，第一个会议可能是从八点开到晚上八点的长会，你选了它，后面全废。而按右端点升序，第一个一定是结束最早的短会，选它几乎不会错。这就是排序维度的威力——它决定了你"第一眼看到的是哪个候选"，而贪心的本质就是"每次看第一个候选并做决定"。

我踩过最惨的一次坑，是一道"删除最少区间使剩余不重叠"的题。我按左端点排完，遇到重叠就删右端点大的，结果在一个用例上挂了。后来发现，当两个区间左端点相同时，按左端点排序的相对顺序是不稳定的，导致删除决策出现歧义。正确做法是按左端点升序、右端点升序做二级排序，才能保证"左端点相同的情况下，短区间在前"，删除逻辑才自洽。

2.2 右端点升序的适用边界

右端点升序是"不重叠选取"类问题的黄金排序，但它不是万能的。它的适用前提是：你关心的是"给后面留多少空间"，而不是"当前区间覆盖了多宽"。

一旦题目的目标变成"覆盖"而不是"选取"，右端点升序就失灵了。比如"用最少区间覆盖 [0, 10]"，你按右端点排，第一个可能是 [8, 9]，它右端点小但根本盖不住开头，选它毫无意义。这类题必须按左端点升序，因为你要保证"从目标段的最左端开始，一步步往右推"。

所以排序维度的选择，本质上是由目标函数决定的：目标是"数量最多/冲突最少"，看右端点；目标是"覆盖完整/推进最远"，看左端点。这个对应关系我建议直接记死，考场上能省大量推导时间。

2.3 二级排序与稳定性：那些藏在细节里的坑

单维度排序不够用时，就得加二级排序。最常见的组合是"左端点升序 + 右端点升序"和"右端点升序 + 左端点降序"。

前者用于合并、删除类问题，保证左端点相同时短区间优先，避免长区间"吃掉"短区间导致误删。后者用于"不重叠选取"的某些变种，比如当右端点相同时，你希望左端点大的（更短的）排在前面，这样选它占用的空间更少。

这里有个特别隐蔽的坑：很多语言的内置排序是不稳定的（比如某些实现对对象数组的排序），如果你只按一个维度排，相同键值的元素相对顺序可能被打乱，导致结果不可复现。我的习惯是永远显式写全比较逻辑，哪怕看起来多余。多写一行比较函数，比事后 debug 半小时划算得多。

# 不重叠选取：右端点升序，右端点相同则左端点降序（更短的优先） intervals.sort(key=lambda x: (x[1], -x[0])) # 合并/删除：左端点升序，左端点相同则右端点升序（短的在前） intervals.sort(key=lambda x: (x[0], x[1]))

3. 三类模型的贪心策略拆解

3.1 不重叠选取：能选就选背后的交换论证

"最多不重叠区间数"的策略简单到令人怀疑：按右端点升序，维护一个"上一个选中区间的右端点"，遍历时只要当前区间左端点不小于它，就选它并更新。

为什么这样对？用交换论证能说清楚：假设最优解里第一个区间不是结束最早的区间 A，而是另一个区间 B。因为 A 的右端点不大于 B 的右端点，把 B 换成 A 之后，A 的左端点一定不小于"起点"（否则 A 根本不在候选里），且 A 的右端点更小，给后面留的空间更大，所以替换后不会让解变差。既然总能替换成"选 A"，那贪心选 A 就是安全的。

这个论证的关键在于"右端点更小意味着给后面留的空间更大"。你可以把它想象成排队：每个人都想早点结束好让下一个人上，结束最早的那个人先上，队伍能过的人最多。这个类比虽然粗糙，但抓住了本质。

实操时有个细节要注意：判断条件是当前左端点 >= 上一个右端点，还是>？这取决于题目对"端点重叠"的定义。会议室安排里，一个会 10 点结束、下一个 10 点开始，通常算不冲突，用>=。但有些题明确说"端点相接也算重叠"，那就得用>。这个边界一定要看题面，我因为>=和>搞反挂过至少三次。

3.2 区间覆盖：在可达范围内选最远的

"用最少区间覆盖目标段 [start, end]"是另一大类。策略是：按左端点升序，维护当前已覆盖到的右边界cur，在所有左端点不大于cur的区间里，选右端点最大的那个，选完把cur更新为它的右端点，计数加一，直到cur >= end。

这个策略的直觉是"每一步都尽量往右推"，因为推得越远，需要的区间越少。但实现时有个容易忽略的点：如果某一轮里没有任何区间的左端点不大于cur，说明出现了断层，直接返回失败。这个断层检测是很多人的盲区，写完忘了判，遇到无解用例就死循环或返回错误值。

还有一个变种是"覆盖 [0, n] 需要的最少区间数，区间可以重复使用"，这时候策略不变，但要注意循环终止条件和计数逻辑。我一般会先画一条数轴，把cur标出来，手动模拟一遍，确认断层检测和终止条件都对，再写代码。

def min_cover(intervals, start, end): intervals.sort(key=lambda x: x[0]) count = 0 cur = start i = 0 n = len(intervals) while cur < end: best = cur # 在所有左端点 <= cur 的区间里找右端点最远的 while i < n and intervals[i][0] <= cur: best = max(best, intervals[i][1]) i += 1 if best == cur: # 断层，无法推进 return -1 cur = best count += 1 return count

3.3 合并与删除：维护当前区间，比较右端点做决策

合并重叠区间是入门题，但它的"删除最少使不重叠"变种才是真正拉开差距的地方。合并的策略是：按左端点升序，维护当前合并区间[l, r]，遇到新区间时，如果它的左端点不大于r，说明重叠，把r更新为max(r, 新区间右端点)；否则把当前区间收进结果，换新区间。

删除变种（最少删除多少个区间使剩余不重叠）的策略稍有不同：按左端点升序，维护上一个保留区间的右端点last_end，遇到新区间时，如果它的左端点小于last_end（重叠），就必须删一个。删谁？删右端点大的那个，因为右端点大意味着占用空间多、更容易和后面冲突。所以如果新区间右端点更小，就"替换"掉上一个（相当于删上一个），否则删当前。

这里有个反直觉的点：删除变种里，"替换"操作意味着计数不变但保留的区间变了。很多人写成"删当前"就完事，结果在"长区间在前、短区间在后"的用例上多删了。正确逻辑是保留右端点更小的那个，计数加一（因为总得删一个），但保留的区间要更新。

4. 从会写到写对：边界与反例的实战排查

4.1 端点开闭：一个符号决定对错

区间题最阴的坑就是端点开闭。[1,2]和[2,3]到底重不重叠？不同题目定义不同。会议室安排通常认为不重叠（端点相接不算冲突），但"合并区间"通常认为重叠（因为要合并成[1,3]）。这个差异直接决定了你用<=还是<。

我的做法是：拿到题先找题面里"重叠""冲突""相接"这些词的定义，找不到就看样例。如果样例里有两个端点相接的区间且结果体现了某种处理方式，那就以样例为准。实在模糊，就按"端点相接算重叠"处理（更保守），因为大多数合并类题目是这个语义。

注意：不要凭记忆套模板。我见过太多人因为把会议室安排的>=套到合并区间上，导致[1,2]和[2,3]没合并，直接 WA。

4.2 空输入、单区间、全重叠：三类必测用例

写完代码别急着提交，先跑这三类用例：

• 空输入：返回空结果还是 0？很多题对空输入有明确要求，不测就挂。
• 单区间：贪心循环能不能正确处理只有一个元素的情况？有些实现会在循环条件上出问题。
• 全重叠：所有区间互相重叠，比如[[1,10],[2,3],[4,5]]，检验你的"删谁/合并谁"逻辑是否真的按右端点比较，而不是按输入顺序。

全重叠这个用例特别能暴露问题。我调试"删除最少"那道题时，就是靠[[1,10],[2,3],[4,5]]发现自己的替换逻辑写反了——正确答案是删[1,10]留两个短的，但我一开始删了后面两个，因为没比较右端点。

4.3 贪心失效的反例构造法

有时候你不确定能不能贪，最快的验证方式是主动构造反例。方法很简单：想一个"局部最优但全局吃亏"的场景。

比如"带权区间调度"，构造[[1,3] 价值 100, [2,4] 价值 1, [3,5] 价值 100]。按右端点贪心会先选[1,3]（价值 100），然后[3,5]（价值 100），总共 200，看起来对。但换个例子[[1,4] 价值 100, [2,3] 价值 1, [3,5] 价值 1]，贪心选[1,4]得 100，而最优是选[2,3]和[3,5]得 2——等等，这里贪心反而更优。真正让贪心失效的是[[1,2] 价值 1, [2,3] 价值 1, [1,3] 价值 3]：贪心按右端点先选[1,2]和[2,3]得 2，但最优是选[1,3]得 3。这个反例一构造出来，立刻就知道这题不能贪，得上 DP。

构造反例的能力，比背十道题的模板都值钱。因为它让你从"记忆"升级到"判断"，遇到新题也能快速定性。

5. 我在实战中攒下的几条硬经验

5.1 先画数轴再写代码

这是我带人时反复强调的习惯：拿到区间题，先在纸上画一条数轴，把样例区间标上去，手动模拟贪心过程。画的过程会逼你想清楚"当前处理到哪了""边界怎么更新""重叠怎么判"。很多人上来就写代码，写到一半发现策略不对，推倒重来，反而更慢。

画数轴还有个好处：能直观看出排序维度对不对。如果按某个维度排完，数轴上的区间顺序看起来很别扭（比如长区间总在前面挡路），那大概率排序维度选错了。

5.2 计数与状态更新分离

贪心代码里最容易出 bug 的地方，是"计数"和"状态更新"混在一起写。比如删除变种里，你既要把count加一，又要更新last_end，还要决定保留哪个区间，三件事搅在一起，逻辑一乱就错。

我的习惯是把它们拆开：先判断"要不要操作"（是否重叠），再决定"操作谁"（保留哪个），最后"更新状态"（last_end和count）。每一步单独一行，加注释。代码看起来啰嗦，但调试时一眼能看出哪步错了。这个习惯让我在比赛里少挂了很多次。

5.3 用"不变量"自检

每写完一个贪心，我都会问自己：循环过程中，我维护的那个变量代表什么？它是不是始终满足某个不变量？比如不重叠选取里，last_end始终是"已选区间的最小右端点"；覆盖问题里，cur始终是"当前能覆盖到的最右位置"。如果某次更新后这个不变量被破坏了，说明逻辑有问题。

这个自检方法比跑用例更根本，因为它检验的是逻辑正确性，而不是某几个特定输入。我建议每个学贪心的人都养成这个习惯——写之前先想清楚不变量是什么，写完之后对着代码验证它是否始终成立。

5.4 什么时候该果断放弃贪心

最后说个心态问题：不是所有区间题都能贪，也不是所有能贪的题都值得现场推导。如果构造反例花了五分钟还没结论，或者题目明显带"权值""多种选择""需要记录路径"，那就别硬贪，直接上 DP 或者搜索。贪心的性价比在于"想清楚之后代码极短"，但如果"想清楚"这一步卡住了，硬耗下去不如换个思路。

我个人的经验是：能用一句话说清"为什么这样选不会更差"的，才用贪心；说不清的，一律 DP。这句话听着简单，但能帮你省下大量考场上的纠结时间。区间贪心说到底是一门"取舍的艺术"，而取舍的前提，是你真的知道自己为什么这么取。