如果你和我一样按专题刷题大概率会遇到一个现象贪心这一章里区间问题简直像开了单独的分区。区间选点、最大不相交区间数量、区间分组、区间覆盖四道题长得都很像都是给你一堆[l, r]的区间都要求一个最优值但解法一个跟一个不一样。我第一次刷到这里的时候前两道还能顺着下来到区间分组就开始混最后区间覆盖差点直接背板子。后来多做了几轮我才意识到这四道题本质上是同一套分析框架下的四个分支只要把“按哪个端点排序、为什么按这个端点”想明白代码其实都很短。这篇文章就把这四道题放在一起讲透包括每个问题的贪心直觉、正确性为什么成立、完整 C 实现以及我实际刷题和带新人时最容易踩的坑。如果你也正在被区间题折磨或者想彻底分清这四种套路这篇应该能帮你省不少时间。1. 先建立统一框架区间题到底在贪什么1.1 四道题不是四套知识点是一套思考顺序很多人一开始学区间贪心喜欢把四个问题当成四个孤立模板去背。我的建议恰恰相反先别急着记结论先问自己一个问题——每个区间只有左右两个端点如果要做贪心决策点一定在端点上。为什么这么说区间内部的点对于“是否冲突”“能否覆盖”这类判断没有区分度真正决定两个区间关系的是l和r的大小顺序。所以区间类贪心的核心就一句话选一个合适的端点作为时间线把区间按它排好序然后从左到右扫描在每一步做只依赖当前端点大小的局部最优选择。这个框架可以套到下面所有题上差别只在于排序看左端点还是右端点扫描时需要维护的信息是“一个点”“一个右端点”还是“一组右端点”判断冲突/覆盖用的是、、还是。区间选点和最大不相交区间数量特点是从左往右顺着右端点走一个“当前已覆盖到哪”的变量就能控制全局区间分组必须同时关心很多条组内时间线所以要引入优先队列区间覆盖沿着左端点推进但每一步要临时回头看一堆候选区间所以用双指针。这样看它们并不是四个独立考点而是同一个思考框架在不同约束下的展开。1.2 排序方向决定了百分之八十的成败我见过太多人代码逻辑写得完全正确就是排序排错了导致答案差之千里。判断排序方向有一个很实用的经验如果贪心决策依赖的是“尽可能利用已经发生的结束时间”通常按右端点升序如果贪心决策依赖的是“从起点开始一步步向前推进覆盖边界”通常按左端点升序。这个经验不是万能公式但覆盖了这四道题的全部情况。再往深一层说排序本质上是给所有区间建立一个统一的处理顺序让扫描过程的每一步都只和“已经处理完的集合”比较而不会受到未来区间的影响。如果排序方向反了信息就会出现“倒挂”比如一个右端点很大的区间先被处理它会把当前覆盖边界顶得很远导致后面真正应该先被覆盖的短区间被误判为“已经覆盖了”。这就是很多人把区间选点排成左端点后莫名其妙 WA 的原因。2. 区间选点为什么“每个点都尽量靠右”是最优的2.1 问题定义与第一直觉区间选点的标准题面是给定N个闭区间[l_i, r_i]在数轴上选尽量少的点使得每个区间内至少包含一个被选的点求最少点数。我最早看到这题的第一反应是那就数轴上的端点都试一试呗反正点只能放在覆盖最多区间的位置。但后来意识到这种“求最大覆盖位置”的思路在多个区间嵌套时会非常难处理因为你不知道每个点到底是为了满足哪个区间而存在的。正确的贪心是按右端点从小到大排序然后从左到右扫描。如果当前区间没有被已经选择的点覆盖就在当前区间的右端点放一个点。为什么选右端点而不是左端点或者中点因为对于一个还没被覆盖的区间只要你在这个区间内放点它就能被覆盖而右端点是这个区间里“最靠右”的位置放这里能让这个点尽可能多地覆盖到后面那些左端点较小、右端点较大的区间。换句话说同样的一个点放在右端点能覆盖的范围是“从现在到更后的未来”放在左端点可能连当前这个区间之后紧跟的区间都顾不到。2.2 正确性证明交换论证一次讲清我从教材里学到的证明方法叫交换论证虽然名字听起来吓人但思路特别朴素非常适合用来说服自己贪心没错。考虑右端点最小的那个区间[l_min, r_min]。这个区间无论如何都必须被覆盖所以在最终方案里至少有一个点落在它内部。既然必须有点落在[l_min, r_min]内部我们完全可以把那个点移动到r_min这个位置而不影响它原本覆盖的所有区间吗答案是可能影响。仔细想这一步。一个点原本在[l_min, r_min]内部某个位置x它覆盖了若干个左端点 x 右端点的区间。如果把点移到r_min那么原来被它覆盖的区间中右端点小于r_min的那些会不会失盖不会因为r_min本身是全局最小的右端点所有区间的右端点都大于等于r_min所以原有点覆盖的区间右端点都大于等于r_min。再看这些区间的左端点如果它们的左端点小于等于x那么移动点后点的位置变大了仍然可能大于某个区间的左端点吗万一某个区间左端点在x和r_min之间这个区间原本被覆盖移动后点反而落在它的左边就会失盖。这个反例确实存在所以上面的“无条件右移”论证是不严谨的。那为什么实际贪心还是对的关键在于贪心决策的语境不同我们在确认一个区间需要新放点时只考虑“这个区间内部还没有点”的情况。此时之前已经放过的点都在更左边当前区间是第一个没被覆盖的。为了覆盖它我们新放的点放在它的右端点不会破坏已经覆盖过的区间因为所有已放点都在当前区间左端点左边新点在右端点两者互不影响。对后续未被处理的区间右端点是最靠前的位置覆盖范围最大。这样用归纳法每一步的最优局部选择不会让后续状态变差贪心成立。更严格的证明写法是用“第一个需要放点的区间”的归纳第一个区间右端点最小必须有点落在它内部把它放在右端点能覆盖所有后续左端点小于等于r_min的区间中的一部分对剩下未被覆盖的区间问题规模缩小继续按同样办法处理。这个“第一个区间必须被覆盖点在右端点不劣”的论证才是区间选点正确性的根。2.3 完整实现与两个易错点先看代码很短。#include bits/stdc.h using namespace std; const int N 100010; struct Range { int l, r; bool operator (const Range W) const { return r W.r; // 按右端点升序 } } ranges[N]; int main() { int n; scanf(%d, n); for (int i 0; i n; i) { scanf(%d%d, ranges[i].l, ranges[i].r); } sort(ranges, ranges n); int res 0; int last -2e9; // 记录上一个被选点的位置 for (int i 0; i n; i) { if (ranges[i].l last) { // 当前区间没有被覆盖在右端点放新点 res; last ranges[i].r; } // 若 l last说明 last 就在这个区间内部已经被覆盖 } printf(%d\n, res); return 0; }这里有两个点我一开始经常错。第一判断条件是l last而不是l last。因为题面给的是闭区间当last恰好等于l时这个点就在区间的端点属于区间内部所以应该算覆盖。用会无端多加一个点。类似这种细节笔试里很容易被隐藏用例卡住。第二last初始化成极小值比如-2e9。很多同学写成0或者-1如果区间坐标本身就是负数第一个区间就会被误判为“已被覆盖”然后少算一个点。这类初始化越界值建议用-2e9、-4e18这种明显超出题目数据范围的值宁可离谱也不要贴着边界。3. 最大不相交区间数量换个说法几乎是同一道题3.1 问题定义最多能选几个互不重叠的区间题目通常会这样问给定N个区间选出尽量多的区间使得选出的区间两两没有公共部分端点重合也算重叠因为闭区间的交点算公共点求最多能选多少个。这就是经典的“活动安排问题”一个人一天只能参加一场活动每场活动有起止时间问最多参加几场。我第一次做这题时觉得它和区间选点应该有关但说不上来。后来才发现两者在数学上是一对互相印证的模型区间选点的最少点数等于最大不相交区间数量。这个结论可以用“每个点对应一个被选区间”来建立映射但更直观的理解方式还是回到贪心本身。3.2 贪心策略每次选结束最早的区间正确做法是按右端点升序排序依次扫描如果当前区间与上一个被选中的区间不冲突左端点大于上一个被选区间的右端点就选中它。直接给反例说明为什么不能按左端点排序。考虑三个区间[1, 10]、[2, 3]、[4, 5]。按左端点排序后排序结果是[1,10]、[2,3]、[4,5]贪心会先选[1,10]然后[2,3]和[4,5]都与它重叠于是答案只有 1。但正确答案显然是选[2,3]和[4,5]得到 2。问题出在哪按左端点排序会被一个“开始很早但持续很长”的区间迷惑它看似最先出现却是最差的选择。按右端点排序后先处理[2,3]再处理[4,5]最后[1,10]与[4,5]冲突不选得到 2。为什么选结束越早越好因为区间的结束时间决定了对后续区间的“挤压程度”结束得越早留给后面的空间越大。这就是生活中的直觉——一天里先安排最早结束的那场活动往往能塞进去更多活动。正确性证明同样用替换论证在某个最优解里右端点最小的区间如果没被选那么用这个最小右端点区间替换最优解中“第一个被选的区间”区间数量不变且不会与后面的区间产生新的冲突因为替换后的区间结束时间更早后面接得只会更轻松。于是最优解可以被逐步替换成贪心解贪心解就是最优解。3.3 代码和区间选点几乎一模一样#include bits/stdc.h using namespace std; const int N 100010; struct Range { int l, r; bool operator (const Range W) const { return r W.r; } } ranges[N]; int main() { int n; scanf(%d, n); for (int i 0; i n; i) { scanf(%d%d, ranges[i].l, ranges[i].r); } sort(ranges, ranges n); int res 0; int lastR -2e9; // 上一个被选中区间的右端点 for (int i 0; i n; i) { if (ranges[i].l lastR) { res; lastR ranges[i].r; } } printf(%d\n, res); return 0; }对比区间选点的代码你真的会发现它们连if条件都一样只是last的含义从“上一个被选点的位置”变成了“上一个被选区间的右端点”。这两道题我后来干脆当成同一题不同的问法来处理只要代码写出来横竖都是那个套路。这里仍要注意闭区间语义判断条件是l lastR也就是左端点严格大于上一个右端点才能选。如果写成l lastR遇到[1, 2]和[2, 3]这样的数据会把端点重合的两个区间都选上结果必然 WA。很多题解会把这种情况单独拿出来讲就是因为闭区间问题和开区间问题差的就是这一个符号写反了很难意识到。3.4 与区间选点的关系一个快速自检的等价性我刷题时发现一个特别好用的自检技巧把区间选点题目的输出和最大不相交区间数量的输出对比一下理论上应该完全一致。为什么因为“最少选点数覆盖所有区间”和“最多选互不相交区间数”在区间图里互为对偶最少的点可以看成把每个点“扩展”成一个被选区间反过来每个互不相交区间可以派一个代表点。这个等价性不是本文的严格证明重点但你可以拿任意随机数据跑一下两套代码输出相同心里就踏实很多。我在带新人时经常让他们先做这个“双解对比”一旦发现两个代码答案不一致一定是某个符号写错或者排序方向错了。这个排查思路比对着数据猜边界高效得多。4. 区间分组优先队列登场贪心不再是单点后移4.1 问题定义最少几间教室区间分组的经典表述是给定N个区间表示一批活动的时间段同一间教室同一时间只能安排一个活动问最少需要多少间教室才能容纳所有活动。用术语说就是对区间集合进行分组每组内部的区间两两不相交求最小分组数。这个问题表面上看和“最大不相交区间数量”很像但有一个本质区别上一问是一天只能参加一场活动问最多参加几场这一问是一个教室一天可以排很多场但同一时间不能并行问一共需要几个教室。一个是“从所有活动中挑”一个是“把所有活动都排进去”。4.2 按左端点排序 小根堆维护“各组最后的结束时间”区间分组的贪心策略是按左端点升序扫描所有区间维护一个最小堆堆里存的是每个组当前最后一个区间的右端点。对于当前区间看堆顶也就是所有组中“最后结束时间最早”的那个组如果堆顶小于当前区间的左端点说明这个组在新区间开始之前已经空闲了可以复用否则说明所有组都还在忙当前区间必须新开一组。这里我先解释一下为什么按左端点排序。因为我们要模拟时间从早到晚流动扫描到某个区间时所有起点更早的区间已经分配到各组了。一个组能不能接纳当前区间只需要看这个组“最近一次活动结束得有多晚”。如果最早的结束时间都晚于当前区间的开始时间那么其他组结束得更晚当前区间当然不能进任何已有组。这个判断依赖“当前区间的左端点”作为时间基准所以必须按左端点升序来处理让扫描顺序和时间线一致。再解释为什么用堆而不是数组维护每组的“最后右端点”会随着新区间加入而更新我们需要频繁查询所有组中的最小值还要把一个值更新成更大的值。用普通 vector 每次找最小值是 O(n)整体会退化到 O(n²)用小根堆每次查询和更新都是 O(log n)总复杂度 O(n log n)稳稳通过10^5级别数据。4.3 手推一个完整例子拿一个容易混的样例来走一遍[1, 4]、[5, 6]、[2, 3]。先按左端点排序[1,4]、[2,3]、[5,6]。处理[1,4]堆空新开一组push4堆为{4}。处理[2,3]堆顶44 2不成立说明所有组在2时刻都还在忙唯一的组要到4才空新开一组push3堆为{3, 4}。处理[5,6]堆顶33 5成立说明[2,3]这组在5之前已经空闲可以复用。弹出3push6堆变为{4, 6}。最终堆的大小是2答案就是 2。方案是教室 A 排[1,4]教室 B 排[2,3]和[5,6]。注意[2,3]和[5,6]能被分到同一组是因为3严格小于5中间有空档。如果活动时间改为[2,5]和[5,6]由于闭区间在5这个点重叠它们就不能同组这时heap.top() l的条件是5 5不成立会强制新开一组。这个细节恰恰是分组题翻车率最高的地方。4.4 完整实现与复杂度#include bits/stdc.h using namespace std; const int N 100010; struct Range { int l, r; bool operator (const Range W) const { return l W.l; // 按左端点升序 } } ranges[N]; int main() { int n; scanf(%d, n); for (int i 0; i n; i) { scanf(%d%d, ranges[i].l, ranges[i].r); } sort(ranges, ranges n); priority_queueint, vectorint, greaterint heap; // 小根堆 for (int i 0; i n; i) { if (!heap.empty() heap.top() ranges[i].l) { // 最早空闲的组可以复用 heap.pop(); heap.push(ranges[i].r); } else { // 所有组都还在忙新开一组 heap.push(ranges[i].r); } } printf(%zu\n, heap.size()); return 0; }复杂度排序 O(n log n)每个区间一次堆操作 O(log n)总复杂度 O(n log n)空间 O(n)。这里有个小细节输出堆大小的格式用%zu如果你写%d会收到一堆类型不匹配警告虽然很多环境下能跑但 clang 下会报警告建议养成好习惯。4.5 为什么按右端点排序在这里会翻车我之前有段时间混淆分组和选点觉得“既然是找最早空闲那就按右端点排序先处理最早结束的不好吗”后来构造出一个反例才彻底明白。考虑两个区间[1, 4]和[5, 6]。正确答案显然是 1 组这俩不重叠。但如果你按右端点升序先处理[5, 6]堆变成{6}再处理[1, 4]堆顶6 1不成立只能新开一组答案变成 2错误。问题出在按右端点排序后处理顺序不再随时间线推进。处理[1, 4]时[5, 6]这组虽然已经“结束”了但在时间线上它还没开始堆里的6是未来事件却被当作“当前最早空闲时间”用来判断。这就是我把排序方向看成核心决策点的原因——分组问题的判断必须站在“当前时刻”看哪组已经空闲只有左端点排序才能保证扫描时刻单调递增。5. 区间覆盖每次挑“能接上且最远”的那一个5.1 问题定义用最少的区间铺满一个大区间区间覆盖题面给定一个目标大区间[s, t]以及若干小区间每个小区间可以重叠也可以用超出目标边界的部分问最少选几个小区间能把[s, t]完整覆盖。如果不能覆盖输出-1。一个更贴近生活的类比是你有一段[0, 24]的全天值班表手上有若干人的空闲时段选择最少的几个人排满全天。注意允许有人从6点干到30点超过当天边界也行只要把[0, 24]这段覆盖住就算成功。5.2 贪心策略从起点出发每次选能接上的区间里右端点最大的做法先把所有区间按左端点升序排序。然后从current s开始每次在“左端点不超过current”的所有区间里选一个右端点最大的区间把current更新成这个右端点。重复这个步骤直到current t。为什么这个贪心正确因为在保证能连接当前已覆盖范围的前提下把所有候选区间放在一起比较选右端点最大的一个能让覆盖范围推进得最远。后面需要的区间数只会变少不会变多。和“选点”里“把点放在右端点”的道理一脉相承越是把边界往右推越容易覆盖更多。证明依然是归纳法假设当前覆盖到了current任何可行方案都必须选某个左端点 current的区间来延续覆盖选其中右端点最大的区间剩余覆盖任务不会比选其他区间更困难因此局部最优不破坏全局最优。实现上要注意一个细节不能每轮都重新遍历所有区间找最大右端点那会变成 O(n²)。正确做法是利用排序后的单调性用双指针维护“当前覆盖范围内尚未被考虑过的区间”。5.3 双指针写法与无解判断先看代码#include bits/stdc.h using namespace std; const int N 100010; struct Range { int l, r; bool operator (const Range W) const { return l W.l; } } ranges[N]; int main() { int s, t; scanf(%d%d, s, t); int n; scanf(%d, n); for (int i 0; i n; i) { scanf(%d%d, ranges[i].l, ranges[i].r); } sort(ranges, ranges n); int res 0; int current s; int i 0; bool ok false; while (i n) { int maxR -2e9; // 在左端点 current 的区间里找右端点最大的 while (i n ranges[i].l current) { maxR max(maxR, ranges[i].r); i; } // 没有能接上的区间说明中间有断层 if (maxR current) { break; } // 选这个能延伸到最远的区间 res; current maxR; if (current t) { ok true; break; } } if (ok) printf(%d\n, res); else printf(-1\n); return 0; }这个写法我有两个印象很深的经验。第一内层while里i只增不减因为current只会变大所以一个区间一旦满足l current被考虑过之后所有时刻它依然满足l current不会被漏掉但如果不及时消耗这些区间外层while每次都会从头扫复杂度就爆炸了。第二内层扫描结束后maxR current的判断非常关键。可能你以为“只要有区间能接上就一定有解”其实不一定有可能候选区间的右端点等于甚至小于current那选它没有任何推进作用反而白白消耗一个区间。比如当前已经覆盖到10候选区间是[8, 10]它能接上但不推进如果选了它会陷入死循环。所以必须检测这次扫描是否让current真正变大了如果maxR current直接判定无解。补充一个边界第一个区间开始处理时current s内层扫描会把所有l s的区间纳入候选。如果第一个候选区间就选不出所有l都大于s说明起点本身没被覆盖直接就是 -1。这个判断被“maxR current就 break”统一覆盖了因为此时maxR不会被更新仍然是-2e9。5.4 覆盖题最容易忽略的“已选区间记录”有些题目不只要输出最小数量还要输出具体覆盖方案。此时在更新maxR的循环里需要顺带记录“当时造成maxR最大的区间下标”。注意是记录下标而不是记录左端点因为后面输出方案时要按选中的区间顺序打印。记录方式很简单在内层while里每次发现ranges[i].r maxR时把当前下标赋值给bestIdx当选完本轮后把bestIdx存入答案数组。这个操作不会增加复杂度但能显著提升代码的实用度。实战中我遇到过不少题目从“求数量”变成“求方案”只有把记录逻辑提前写好才能快速改出来。6. 四道题的横向对比从题目句子到算法的判别流程6.1 一张速查表我后来把四道题的判别方式浓缩成一张表刷题时用来对照很少再混淆问题典型问法排序依据核心操作关键判断区间选点最少选几个点使每个区间至少含一个点右端点升序记录上一个点位置lastl last则选点最大不相交区间最多选多少个互不相交的区间右端点升序记录上一个选中区间的右端点lastRl lastR则选区间区间分组至少分几组每组内部区间互不相交左端点升序小根堆存各组最后右端点heap.top() l则复用组区间覆盖最少选几个区间覆盖[s, t]左端点升序双指针找当前可接上的最大右端点maxR current则无解这张表我贴在自己笔记里每次做题前先对着表找“类型”再看具体细节。用熟之后会发现很多变形题本质都是这四个模型的组合或包装。6.2 从关键词快速反推考点我总结了一组判别口诀虽然不完全严谨但作为第一判断非常高效问“最少点” → 区间选点r排序问“最多区间数”“最多活动” → 最大不相交区间数量r排序问“最少组数”“几间教室”“几台机器” → 区间分组l排序 小根堆问“用尽量少的区间覆盖” → 区间覆盖l排序 双指针。如果你遇到一个题目题干一上来是“有 N 个任务每个任务有一个开始时间和结束时间问至少需要几台机器才能完成全部任务”别犹豫就是区间分组。如果同样的题干变成“问最多能完成多少个任务”结果变成了最大不相交区间。同一个数据背景问题最后一行不一样算法就完全不同。我吃过好几次亏才明白读题时一定把最后一句问法圈出来再选模板。6.3 一道混合题的推演我用一个虚构场景把四道题串一遍假设你是某高校实验室的设备管理员设备预约系统里有一批实验申请每个申请是[l, r]区间。如果系统要求“最少选哪些申请可以确保每个时间段至少有一台设备被使用”这是区间选点如果系统要“在某个申请时段内最多能安排多少场不冲突的实验”这是最大不相交区间如果系统要“把所有实验都排进去最少需要几台相同设备”这是区间分组如果系统要“用最少的人值班覆盖一整天的设备看护”这是区间覆盖。四个问题共享同一批区间数据但因为目标不同处理方式完全不同。我自己辅导新人时经常用这个例子做测试效果比直接讲定义好很多。7. 实战中最容易翻车的三个地方7.1 闭区间和开区间一个符号决定生死这四道题默认都是闭区间所以选点/最大不相交判断是l last分组复用是heap.top() l覆盖可接是l current。但如果题目说“左闭右开”所有判断都要翻转最大不相交变成l lastR端点重合时可以共存分组变成heap.top() l上一个结束时刻恰好等于新区间开始时可以同组覆盖可达条件变成l current因为左端点等于当前边界时只能覆盖到开边界实际不算连上。这种题往往藏在一些变种题面里比如“活动从时刻l开始到r结束结束时刻可以马上开始下一个活动”。它就相当于开区间语义。我建议每道题写之前先问自己端点重合到底算不算冲突把这一点固化成一行的注释写在代码顶部能少交很多次罚时。7.2 排序比较器别写反容易 WA 得莫名其妙用sort对结构体排序最稳的写法是重载并且保证严格弱序。我见过有人直接写bool operator (const Range W) const { return r W.r; }这个没问题。但如果你按右端点排完还想按左端点排容易写成bool operator (const Range W) const { return l W.l r W.r; }这是典型的错误写法。l W.l r W.r不满足严格弱序中的传递性要求sort行为未定义结果可能不对。正确写法是bool operator (const Range W) const { if (l ! W.l) return l W.l; return r W.r; }另外分组题的小根堆里存的是单独的int右端点不需要额外定义比较器用greaterint就行。覆盖题如果不记录具体方案也不需要自定义结构体比较器。7.3 数据范围与时间复杂度意识很多人学这四道题时只记了模板没养成为复杂度把关的习惯。实际上四个模型的标准解都是 O(n log n)瓶颈在排序和堆操作。如果数据范围到了10^6甚至10^7O(n log n) 依然可行但要注意别在循环里反复申请priority_queue那会引入大量内存分配开销。我踩过的一个真实坑是在一道覆盖题里数据范围s和t达到10^9候选区间n是10^5我用数组下标做覆盖标记直接越界崩溃。后来改成排序 双指针瞬间跑过。所以结论是当坐标范围远大于n时不要试图模拟整个数轴一定回到贪心扫描本身。7.4 从“背模板”到“自己会选模板”的最后一公里有段时间我对四个模板的代码已经滚瓜烂熟但遇到某题还是容易套错。后来我找到的办法是把四道题打乱顺序每做一道新题都先强制自己写两行注释// 目标最少点/最多区间/最少组/最少覆盖 // 排序r 还是 l维护什么数据结构这两行写不出来就不写代码。这个方法听起来很笨但它逼着我把问题归类和算法选择变成显式思考而不是靠“上一题做的是分组这题应该也差不多”的错觉。带过的几个低年级同学用这个办法练习两到三周后正确率提升都很明显。另外关于这四道题的证明我的体会是把“为什么贪心这一步不会让后面的结果更差”想清楚比记住反例重要得多。因为笔试不一定会考原题但它一定考察你有没有真的理解贪心选择的“诱因”。比如覆盖题你的诱因是“右端点越远覆盖推进越多”这个理由在任何新的覆盖题里都成立这比死记“左端点排序后双指针”能应对更多的变体。最后再分享一个我很常用的自测组合每次写完一段贪心代码我都会立刻构造三组数据。第一组所有区间都互不相交第二组所有区间完全重叠第三组一个区间包住其他所有区间。如果三组数据都能得到直觉上正确的答案才提交。这三组数据不复杂但能击穿绝大多数排序方向、端点符号和初始化错误。尤其是“一个包全部”的数据对覆盖题和分组题特别有用因为它能直接暴露推进变量是否被错误更新。养成这个自测习惯之后我的区间题提交一次过率提高了不少。