做算法题这些年我见过太多人在贪心算法上栽跟头的方式了。刷到区间重叠这一块的时候几乎每个人都会经历同一个循环想出一个看起来很有道理的贪心规则写代码提交被一组用例打脸再改再被打脸。区间重叠专题五我想聊的就是这种拉扯感——你越想正向地解决它它越不给你面子可一旦你学会把目标反过来、排序反过来、视角反过来很多卡住半天的问题就像被抽掉了地基一样整面墙自己塌下来了。这篇文章会从活动安排问题讲起拆到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那它选的第一个区间是某个hh的结束时间不早于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。你的贪心解的第一个区间是gg是所有区间里结束最早的。如果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射气球里气球的边界是包含的一支箭射在x2能同时引爆[1,2]和[2,3]所以判断不需要新箭的条件是start arrowPos而判断需要新箭是start arrowPos。下面把常见的两个场景对比一下题目端点相接是否算重叠判断条件435 无重叠区间不算可共存start lastEnd则保留452 射气球算一起引爆start arrowPos才需要新箭253 会议室开会结束与开会开始同时发生时旧会议释放房间start ends[endIdx]才需要新房间每次拿到区间题第一件该做的事就是去题面里找一句话边界是开还是闭。找不到就自己造一组端点为[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的代码骨架几乎一模一样唯一的区别就是一个和一个。但它们的语义完全不同前者在问能不能共存后者在问这一箭能不能同时带走。我在文章第三部分说这是极致拉扯其实拉扯的不仅是逆向思维还有这些看似不起眼却决定生死的边界细节。如果你把这两道题放在一起对比着刷一遍区间重叠题的功力会涨得比刷十道同类型题还快。我自己后来在面试里复盘这类题时最大的体会是贪心算法从来不是猜出来的是先反向定义目标、再证明每一步置换不会变差、最后用边界条件检验出来的。你把这套流程走熟了区间重叠对你来说就不是随风飘摇的直觉而是一条每一步都有据可依的稳定路径。以后再看到贪心两个字脑子里第一反应不该是搏一搏而是我先反过来问问这个局。