贪心算法与区间重叠：逆向思维的三个翻转与实战拆解

做算法题这些年，我见过太多人在贪心算法上栽跟头的方式了。刷到区间重叠这一块的时候，几乎每个人都会经历同一个循环：想出一个"看起来很有道理"的贪心规则，写代码，提交，被一组用例打脸，再改，再被打脸。区间重叠专题（五）我想聊的，就是这种拉扯感——你越想"正向"地解决它，它越不给你面子；可一旦你学会把目标反过来、排序反过来、视角反过来，很多卡住半天的问题就像被抽掉了地基一样，整面墙自己塌下来了。这篇文章会从活动安排问题讲起，拆到LeetCode 435、452、253这三道高频题，最后补上贪心正确性怎么自证、实战里有哪些一碰就炸的细节。它适合刚学完贪心基础、准备系统拿下区间系列的读者，也适合那些刷完题却始终觉得"贪心就是靠猜"的人。至少在这类题上，贪心不是靠猜的，是靠"反着想"的。

1. 逆向思维在区间重叠题里的三个"翻转"

一提到逆向思维，很多人先想到四个字：正难则反。这话没错，但太笼统。我在反复刷区间题之后发现，至少在这个具体场景下，逆向思维可以拆成三个非常具体的翻转动作，每一个都能直接指导你怎么写代码。

1.1 目标翻转：从"选谁留下"到"删谁划算"

区间重叠类题目经常问两件事：最多能保留多少个互不重叠的区间，或者最少删掉几个区间才能让剩下的两两不重叠。"最多保留"和"最少删除"是一体两面，但这两条路的难度完全不一样。

正向求"最多保留"，你的贪心直觉通常是：每次都挑一个最"合适"的区间塞进结果集，然后祈祷这个选择不影响后面的选择。问题来了，"最合适"怎么定义？挑开始最早的？挑结束最早的？挑跨度最短的？在你见过反例之前，根本不知道该信哪个直觉。你可以选一整天，也可以选一个星期，最后还是会被几个精心构造的用例放倒。

反过来，求"最少删除"反而有个特别干净的思路：先把区间按结束时间排好，从前往后扫，只要当前区间和上一个保留的区间重叠，就把当前这个丢掉。同样是给一个数组，正向版本让人抓狂，逆向版本却几乎可以一遍写对。原因在于，"删掉重叠的"本质上是在维护一个"尽量给后面留空间"的保留集合，你不再纠结选哪个最优，而是只盯着"当前这个会不会破坏已经保住的局面"。

1.2 排序翻转：按开始时间排还是按结束时间排

区间问题的第一步永远是排序，而很多人默认按开始时间排。这个习惯不坏，像合并区间这类题目确实需要按开始时间排。可一旦问题跟"选出最大不重叠子集""最少箭射爆气球"这种选择性质有关，按开始时间排序就会把你拖进泥潭。

为什么？因为按开始时间推进时，你永远在看"接下来谁先开始"，而不是"谁先结束"。向前推进的过程中，你必须时刻警惕：当前选中的这个区间会不会把后面更短、更关键的区间挤掉？你在为一个不确定的未来做承诺，而承诺的依据只是"它开始得早"。

按结束时间排序的妙处在于，它把"占用时间线"这个成本压到了最小。你每次选一个结束最早的区间，就相当于把这轮占用的时间缩到最短，把后面最长的连续时段留给剩余的区间。这就是整个区间重叠贪心问题的地基：不是抢着开始，而是抢着结束，好把整个未来让给别人。

1.3 视角翻转：把区间看成线段，还是看成事件

第三个翻转最抽象，也最值钱。区间重叠问题有两种完全不同的可视化方式。

一种是线段的视角：每个区间是时间轴上的一条线段，问题就是怎么摆这些不重叠的线段。另一种是事件的视角：把区间拆成"开始事件"和"结束事件"，让所有事件在同一条时间轴上排队，然后统计任意时刻同时"活着"的事件数量。会议室系列题用第二种视角几乎是降维打击：一间会议室的使用过程可以看成"有人进来 +1、有人出去 -1"，任意时刻的最大并发数就是你需要准备的最少会议室数。这本质上是逆向思维——不从"我有几间房"出发，而从"同一时刻最多有几个会"出发。

这三种翻转做完你会发现，所谓的"逆向思维与区间重叠的极致拉扯"，其实是一场视角的转换：正向走不通，就换目标、换排序、换图形。接下来我把每个翻转放到具体题目里验证一遍，先看最经典的活动安排问题为什么要翻着做。

2. 活动安排问题的翻车现场：正向贪心为什么三条路都走不通

活动安排（也叫会议安排）是区间重叠家族最古老的原型：给你一堆会议的开始时间和结束时间，每个会议都要占用一间完整的会议室，问最多能安排多少场互不重叠的会议。几乎所有后续的区间题都能追溯到这个模型上。我和读者交流时发现，第一次见到这题的人，几乎都会沿着直觉依次踩三个坑。

2.1 坑一：按开始时间最早选

直觉说，开始得越早的会议越应该优先安排，因为这样"不浪费时间"。听着特别有道理。

反例特别简单。今天有三个会：A从8点到12点，B从9点到9点10分，C从9点10分到10点。如果按开始时间最早，你先选了A，从8点一直占到12点，B和C全都没了，最后只能安排1场。可正确解法是先安排B，再安排C，能安排2场。

核心问题是，"开始得早"只保证了占坑早，完全不保证占坑短。你为"早开始"付出的代价，可能是把一整天最精华的时段全部锁死。用一个不严谨但好记的说法：开始早的会，往往是起床最早的会，但不一定是散场最早的会。

2.2 坑二：按持续时间最短选

这个直觉更精致：既然问题出在占用时间太长，那我挑用时最短的不就行了？

这个策略比"开始最早"抗打得多，但依然会翻车。看这组区间：[0,6]、[4,7]、[6,12]。持续时间分别是6、3、6，最短的是[4,7]。按"最短优先"，你先选了[4,7]，接下来[0,6]和它重叠，[6,12]也跟它重叠（6到7这一段），最后只能安排1场。但最优解是[0,6]加上[6,12]，端点正好相接，能安排2场。

原因很简单：一个区间短，只说明它自己短，不说明它挡住别人的数量少。它可能正好横在两个中等长度区间的交界处，把本来能凑在一起的两场全拆散了。这就好像排队打饭，那个买一个包子的人确实快，但他要是站在队中间问东问西，后面一队人都得等他。

常见的错误贪心策略和它们的下场，我整理成一张表：

2.3 为什么"结束最早"一定对：一条给未来让路的逻辑

这里要解释的是，为什么前三个直觉都错，唯独"结束最早"一定对。这也是整个逆向思维最核心的机制。

先看一个反直觉的事实：活动安排问题的最优解里，一定包含那个"结束最早"的区间。你可以这么想——假设某个最优解不包含结束最早的区间g，那它选的第一个区间是某个h，h的结束时间不早于g。现在把h换成g，会发生什么？g结束得比h早，所以g占用的时间段完全落在h的范围内或更早，它不可能跟最优解里h后面的任何区间重叠。换完之后，这个解的大小没变，依然合法，但第一项变成了"结束最早"的g。

这一下就打通了：把g从问题里拿掉，同时把所有跟g重叠的区间都丢掉，剩下的区间构成一个规模更小、结构完全相同的子问题。在这个子问题里，继续选结束最早的，如此循环。每一步都是"局部最优＋给未来让路"，最终得到的方案大小就是全局最优。这个递归式的论证思路，在《算法导论》讲贪心算法时用的是同一个例子，但现在你自己能把它走通了，比看十遍书都管用。

2.4 这三种错误直觉的共同点

你会发现，前三个坑虽然花样不同，本质上是同一个错误：它们都在试图"向前看"，用当下能观察到的属性（开始早、用时短、冲突少）来预测未来。而区间调度的本质是，你永远无法预知未来哪个区间会来，但你能确定一件事——尽早结束，一定不会让未来变得更糟。这就是"反着做"的威力：我不预测明天，我只保证今天不挡明天的路。

3. 三道高频题逆向拆解：从"留下谁"到"射穿谁"再到"挤下几间房"

纸上谈兵结束，来看三道真正高频的面试题。这三道题共享同一个逆向思维骨架，但每一道都有一处关键差异，恰好能把"区间重叠"的边边角角都磨一遍。

3.1 LeetCode 435 无重叠区间：把"删多少"翻成"留多少"

题目是：给定区间集合，删除最少数量的区间，使剩余区间互不重叠。

正向做这道题，你会陷入"删掉哪个才好"的纠结里。逆向的解法非常干净：先求出最多能保留多少个互不重叠的区间，再用总数减去保留数，就是最少删除数。问题的核心从"删"变成了"留"。

class Solution { public int eraseOverlapIntervals(int[][] intervals) { if (intervals.length == 0) return 0; // 按右端点升序排序 Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1])); int keep = 1; // 第一个区间直接保留 int lastEnd = intervals[0][1]; for (int i = 1; i < intervals.length; i++) { if (intervals[i][0] >= lastEnd) { // 当前区间和上一个保留的不重叠，保留它 keep++; lastEnd = intervals[i][1]; } // 否则：当前区间与保留集冲突，丢掉它，lastEnd 不变 } return intervals.length - keep; } }

这里有个细节要说明：排序之后，所有区间的右端点递增。如果当前区间跟上一个保留的区间重叠了，为什么丢掉的是当前这个，而不是上一个？因为上一个的右端点更小，结束得更早，它对后面区间的压迫更小。丢掉"来得晚却更占地方"的那个，是必然的。这就是目标翻转的落地：你不再思考"删哪个最优"，而是思考"保留哪个最不亏"，剩下的全删掉。

顺带一提，这个题里两个区间端点相接（比如[1,2]和[2,3]）算不重叠，可以同时保留，所以判断条件是>=。这一点在第五部分还会重点展开。

3.2 LeetCode 452 用最少数量的箭引爆气球：把"怎么射"翻成"谁可以一箭带走"

这道题是435的变体，但有一个微小却致命的差异。题目是：气球是一个区间[xStart, xEnd]，从某个位置x垂直射箭，能引爆所有满足xStart ≤ x ≤ xEnd的气球，问最少要几支箭。

第一反应可能是"在区间最密集的地方射箭"。这个思路听着对，但"最密集"怎么求？又是下一个坑。逆向做法的核心是：尽量让一支箭带走尽可能多的气球，那么这支箭应该放在哪儿？放在当前这个气球的最右端。

class Solution { public int findMinArrowShots(int[][] points) { if (points.length == 0) return 0; // 按右端点升序排序 Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1])); int arrows = 1; int arrowPos = points[0][1]; // 第一支箭放在第一个气球的右端 for (int i = 1; i < points.length; i++) { if (points[i][0] > arrowPos) { // 这支箭够不到当前气球，必须新射一支 arrows++; arrowPos = points[i][1]; } // 否则这只气球被当前箭带走了，什么也不用做 } return arrows; } }

为什么箭头要放在右端点？因为当前气球是右端点最靠前的气球，任何一支想射穿它的箭，位置x必须满足x ≤ 当前气球的右端点。为了把这支箭的能力最大化，当然要把它推到最右端——放在右端点，既保证射穿当前气球，又最大概率覆盖下一个、下下一个气球的左边界。这就是"局部最优"和"给全局让路"在这道题里的结合：箭放得越靠右，能覆盖的后续气球就越多。

这里的判断条件是>而不是>=，因为题面说xStart ≤ x ≤ xEnd即可引爆，边界是包含的。上一题435里端点相接不算重叠，这一题里气球边界擦一下就炸，所以>和>=的差别直接决定了代码对不对。模板背得再熟，只要没理解这一字之差，451和452这两道题你迟早会交错一次。

3.3 LeetCode 253 会议室 II：把"要几间房"翻成"最多几个会同时开"

这道题问的是：给定一堆会议时间，最少需要多少间会议室。

正向思考会变成一场模拟：会议室A空着吗？不空？B呢？C呢？这种模拟用最小堆也能做，但理解上绕。逆向视角一句话就能戳穿：如果某一时刻有k场会议同时在开，那你至少需要k间房；最少需要的房间数，就是任意时刻最大的同时开会数。

用双指针扫两组排好序的数组，可以把这个"最大并发"干净地算出来：

class Solution { public int minMeetingRooms(int[][] intervals) { int n = intervals.length; int[] starts = new int[n]; int[] ends = new int[n]; for (int i = 0; i < n; i++) { starts[i] = intervals[i][0]; ends[i] = intervals[i][1]; } Arrays.sort(starts); Arrays.sort(ends); int rooms = 0; // 当前已开的房间数 int endIdx = 0; // 指向最早结束的那场会议 for (int start : starts) { if (start < ends[endIdx]) { // 最早结束的会还没散，必须新开一间 rooms++; } else { // 有一间房已经空了，复用，不用新增 endIdx++; } } return rooms; } }

这段代码的妙处在于，它没有任何一间会议室是"被分配"出去的，它只是在数"有多少个会同时活着"。每次有一个会议开始，你就看一眼当前最早的结束时间：如果最早的会还没散，说明所有房间都满着，加一间房；如果已散，你就腾出一间房，指针前进。这里的endIdx每走一步，等于一个会议正式结束，把房间归还。会议同时进行的最大数量，就是这个过程中rooms达到的最大值。

这道题同样可以用扫面线做：把每个区间的开始记为+1，结束记为-1，按时间排序后累加，过程中的最大值就是答案。双指针解法本质就是扫面线的另一种写法，只不过把同类型事件合并排序了。之所以值得放在"逆向思维"专题里讲，是因为绝大多数人看到"最少几间房"会本能地开始模拟房间分配，而不是先问一句：一间房什么时候会被占满？——当你反过来想"什么时候最挤"的时候，答案自己会送上门。

4. 贪心正确性自证：先学会攻击自己，再做交换论证

比做对三道题更重要的，是你到底凭什么相信自己的贪心策略是对的。区间重叠题里，贪心方案普遍短得可怕，也就十几行，所以很多人写完就怀疑：这真的对吗？我给的答案是，每当你设计出一个贪心规则，先做两件事：一是拼命找反例攻击它，二是做一次交换论证。

4.1 学会攻击自己：反例不是运气不好，是构造出来的

反例的构造有套路可循。区间重叠题的贪心翻车，几乎都长一个样：你的规则选了一个"看似合理但居中挡路"的区间，挡住了两个本来可以兼容的区间。比如第二节里的[0,6]、[4,7]、[6,12]，最短优先策略选了[4,7]，它就横在中间，把[0,6]和[6,12]拆散了。

所以拿到一个新贪心规则，你该做的第一件事就是画三个区间：左、中、右。左边一个早早开始早早结束，右边一个晚晚开始晚晚结束，中间一个跨越两者。然后用你的规则走一遍，看它会不会选中间的。如果会，恭喜你，反例找到了。这比在提交记录里被测试用例打脸高效多了。

4.2 最优子结构：贪心成立的第一个支柱

贪心算法能成立通常需要两个性质。第一个叫最优子结构：你把第一步决策做完之后，剩下的问题应该是一个规模更小、结构完全相同的独立问题。

在活动安排里这很直观：你选了结束最早的区间g，然后把所有跟g重叠的区间丢掉，剩下的区间互不影响，等于重新做一次"选最多不重叠区间"的操作。因为子问题和原问题同构，你可以放心递归或循环地使用同一个决策规则。如果去掉一步之后问题变形了，贪心基本就没戏了。

4.3 交换论证的实操姿势：把最优解一步步"掰"成贪心解

第二个支柱叫贪心选择性质：每一步的局部最优选择，至少不会比任何全局最优解差。这个性质的严格证明通常用交换论证。

我把话翻译成人话。假设有一个最优解OPT，它的第一个区间是h。你的贪心解的第一个区间是g，g是所有区间里结束最早的。如果g不在OPT里，我们把h换成g，得到一个新的解OPT'。会不会变差？不会，因为g结束得不晚于h，它占用的时间区间至多和h一样宽，不可能引入新的重叠。这样一换，OPT'的大小没变，依然是最优的，但它的第一个区间变成了g。接下来对第二个、第三个区间重复这个"交换"过程，就能把某个最优解一步步变成你的贪心解，而每一步都没有让解变差。既然贪心解就等于最优解，贪心策略自然是对的。

这套论证看起来很学术，实操起来其实就一句话：你选的每一个元素，都能"顶替"最优解里的某个位置而不产生冲突，那你一直这么选下去，最后就和最优解殊途同归。我在区间题里做自证时只问三个问题：我选的这个区间结束得最早吗？换成它能挡住别人吗？剩下的子问题还是同一个问题吗？三个都是"是"，这代码就可以提交了。

4.4 边界提醒：不是所有区间题都吃这一套

逆向贪心在"最大不重叠子集""最少箭""最少会议室"这类无权重、目标函数只计数的题目上大杀四方，但一旦问题加了权重，比如每个区间的价值不同、求总价值最大，贪心立刻失效，得上动态规划。以后遇到区间题，先问一句：我这个目标是"计数"还是"计分"？计数的可以考虑贪心，计分的还是老实DP吧。

5. 实战排雷：比较器溢出、开闭区间和那一个大于号

最后这部分是真正的血泪教训。区间重叠题的代码骨架全网都是，但照样一堆人提交出错，错法还高度一致。我按踩雷频率从高到低排序讲。

5.1 排序比较器：永远不要直接相减

这是新手最容易踩的雷，尤其452这道题，坐标范围是32位整数的正负边界，a[0] - b[0]一旦溢出，排序结果就是错的，而且错得毫无规律，只在特定的测试数据上爆炸。

// 错误写法：可能会溢出 Arrays.sort(intervals, (a, b) -> a[1] - b[1]); // 正确写法 Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));

就一句话：凡是涉及比较器里的减法，一律换成Integer.compare或者直接用Comparator.comparingInt。算力不值钱，调一个诡异的溢出bug值钱。

5.2 开闭区间：端点相接到底算不算重叠

这是区间重叠题最阴的一个地方，因为判断逻辑只差一个符号。

435无重叠区间里，[1,2]和[2,3]不算重叠，可以同时保留，所以判断"可以保留"的条件是start >= lastEnd。

452射气球里，气球的边界是包含的，一支箭射在x=2，能同时引爆[1,2]和[2,3]，所以判断"不需要新箭"的条件是start >= arrowPos，而判断"需要新箭"是start > arrowPos。

下面把常见的两个场景对比一下：

每次拿到区间题，第一件该做的事就是去题面里找一句话：边界是开还是闭。找不到就自己造一组端点为[1,2]、[2,3]的用例跑一遍，比猜半天靠谱得多。

5.3 空输入和单元素输入：防御性写在最前面

intervals.length == 0的判断几乎每道题都有，但很多人写完主逻辑才发现忘记处理空数组，或者提交之后才被空用例打了一巴掌。单元素数组也一样：435里keep初始化就要考虑首元素，452里第一支箭初始化成第一个气球的右端点，这些写的时候就要想清楚，不要依赖下标边界来"凑巧"通过。

5.4 相同端点的排序稳定性：什么时候会出事，什么时候无所谓

如果两个区间右端点相同，排序时谁在前谁在后，会影响435和452的结果吗？答案是不会。因为你的判断只看下一个区间的左端点和当前保留区间的右端点，右端点相同意味着"当前区间"怎么选都不影响后面的空间。但253的双指针解法要注意另一种情况：某个会议的结束时间和另一个会议的开始时间恰好相同，此时start < ends[endIdx]判断为假，你会先进去复用那间刚空出来的会议室。这正好是对的，因为会议在18点整结束，新会议18点整开始，房间可以无缝交接。如果你用扫面线事件排序实现253，那就必须在同一点的"结束事件"排在"开始事件"之前，顺序反了答案会多算一间会议室。

5.5 那一个大于号，是整篇文章的缩影

435和452的代码骨架几乎一模一样，唯一的区别就是一个>=和一个>。但它们的语义完全不同：前者在问"能不能共存"，后者在问"这一箭能不能同时带走"。我在文章第三部分说这是"极致拉扯"，其实拉扯的不仅是逆向思维，还有这些看似不起眼却决定生死的边界细节。如果你把这两道题放在一起对比着刷一遍，区间重叠题的功力会涨得比刷十道同类型题还快。

我自己后来在面试里复盘这类题时最大的体会是：贪心算法从来不是"猜"出来的，是先反向定义目标、再证明每一步置换不会变差、最后用边界条件检验出来的。你把这套流程走熟了，区间重叠对你来说就不是随风飘摇的直觉，而是一条每一步都有据可依的稳定路径。以后再看到"贪心"两个字，脑子里第一反应不该是"搏一搏"，而是"我先反过来问问这个局"。