区间贪心是算法面试里出镜率极高的一类题但真正让人头疼的不是知道要用贪心而是面对一道新题怎么在十分钟内判断它到底能不能贪、该按什么维度贪。我见过太多人背了一堆模板考场上换个马甲就懵了。这篇内容就是把我这些年刷题、带人、复盘踩坑的经验揉在一起从为什么贪心能成立讲到具体怎么落地再到哪些地方最容易翻车适合刚接触贪心、想系统梳理一遍的读者也适合已经会写但总在边界条件上栽跟头的老手。区间贪心本质上是在一条数轴上做取舍的学问核心关键词就三个区间、排序维度、贪心选择。把这三件事想透绝大多数变种题都能拆开看。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(keylambda x: (x[1], -x[0])) # 合并/删除左端点升序左端点相同则右端点升序短的在前 intervals.sort(keylambda 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(keylambda 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 count3.3 合并与删除维护当前区间比较右端点做决策合并重叠区间是入门题但它的删除最少使不重叠变种才是真正拉开差距的地方。合并的策略是按左端点升序维护当前合并区间[l, r]遇到新区间时如果它的左端点不大于r说明重叠把r更新为max(r, 新区间右端点)否则把当前区间收进结果换新区间。删除变种最少删除多少个区间使剩余不重叠的策略稍有不同按左端点升序维护上一个保留区间的右端点last_end遇到新区间时如果它的左端点小于last_end重叠就必须删一个。删谁删右端点大的那个因为右端点大意味着占用空间多、更容易和后面冲突。所以如果新区间右端点更小就替换掉上一个相当于删上一个否则删当前。这里有个反直觉的点删除变种里替换操作意味着计数不变但保留的区间变了。很多人写成删当前就完事结果在长区间在前、短区间在后的用例上多删了。正确逻辑是保留右端点更小的那个计数加一因为总得删一个但保留的区间要更新。场景重叠时删谁保留区间更新新区间右端点更小删上一个保留新区间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。这句话听着简单但能帮你省下大量考场上的纠结时间。区间贪心说到底是一门取舍的艺术而取舍的前提是你真的知道自己为什么这么取。 
长河君 · 2026/10/31 21:49:55 · 阅读 1.2k 区间贪心算法面试指南：排序维度与贪心策略详解
区间贪心是算法面试里出镜率极高的一类题但真正让人头疼的不是知道要用贪心而是面对一道新题怎么在十分钟内判断它到底能不能贪、该按什么维度贪。我见过太多人背了一堆模板考场上换个马甲就懵了。这篇内容就是把我这些年刷题、带人、复盘踩坑的经验揉在一起从为什么贪心能成立讲到具体怎么落地再到哪些地方最容易翻车适合刚接触贪心、想系统梳理一遍的读者也适合已经会写但总在边界条件上栽跟头的老手。区间贪心本质上是在一条数轴上做取舍的学问核心关键词就三个区间、排序维度、贪心选择。把这三件事想透绝大多数变种题都能拆开看。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(keylambda x: (x[1], -x[0])) # 合并/删除左端点升序左端点相同则右端点升序短的在前 intervals.sort(keylambda 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(keylambda 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 count3.3 合并与删除维护当前区间比较右端点做决策合并重叠区间是入门题但它的删除最少使不重叠变种才是真正拉开差距的地方。合并的策略是按左端点升序维护当前合并区间[l, r]遇到新区间时如果它的左端点不大于r说明重叠把r更新为max(r, 新区间右端点)否则把当前区间收进结果换新区间。删除变种最少删除多少个区间使剩余不重叠的策略稍有不同按左端点升序维护上一个保留区间的右端点last_end遇到新区间时如果它的左端点小于last_end重叠就必须删一个。删谁删右端点大的那个因为右端点大意味着占用空间多、更容易和后面冲突。所以如果新区间右端点更小就替换掉上一个相当于删上一个否则删当前。这里有个反直觉的点删除变种里替换操作意味着计数不变但保留的区间变了。很多人写成删当前就完事结果在长区间在前、短区间在后的用例上多删了。正确逻辑是保留右端点更小的那个计数加一因为总得删一个但保留的区间要更新。场景重叠时删谁保留区间更新新区间右端点更小删上一个保留新区间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。这句话听着简单但能帮你省下大量考场上的纠结时间。区间贪心说到底是一门取舍的艺术而取舍的前提是你真的知道自己为什么这么取。