刷算法题这几年最怕看到两类题一类是动态规划状态转移方程搞死人另一类就是贪心思路看着挺对一提交就WA看完题解才发现自己漏了个反例。不过贪心里面有个很固定的套路就是“区间问题”。区间选点、最大不相交区间数量、区间分组、区间覆盖这四个经典模型几乎每次笔试面试都会以某种变形出现。我把它们全部串起来讲一遍从贪心策略到正确性证明从C代码到边界细节一篇看懂四道题。1. 为什么算法题里总有“区间”的身影1.1 从生活中的调度说起假设你今天有五个会议要排每个会议有开始时间和结束时间你作为会议室的安排人员目标是用最少的会议室把会议全部安排下。这个场景抽象成数学语言就是N个区间[l_i, r_i]区间之间可能有重叠问至少需要几个“容器”来装这些重叠区间。这不就是开会排期嘛。类似的场景还有一台机器加工多个任务每个任务占用的时间段互不重叠最多能安排几个任务一条数轴上要放发射塔需要让每段道路都被某个发射塔覆盖最少放几个塔这些场景的共同点就是输入是一堆线段输出是一个最优数量。算法竞赛和面试特别喜欢这类题因为区间题天然有实际背景代码短但要想全对必须对贪心策略背后的逻辑有充分理解。1.2 四个问题其实是一个家族围绕区间有四道非常经典的贪心题区间选点给定N个区间选最少的点使得每个区间都至少包含一个点。最大不相交区间数量给定N个区间选尽量多的区间使得选出的区间两两不相交。区间分组给定N个区间把所有区间分成尽量少的组每组内部的区间两两不相交。区间覆盖给定一个目标线段[s, t]从N个区间里选尽量少的区间把目标线段完全覆盖。这四道题看上去差别很大但底层用的都是“排序 扫描 贪心决策”这个框架。区别在于排序的键和扫描时的更新规则不同。如果能把四道题的异同讲清楚之后遇到任何区间变形题你都能一眼看出它在考哪个模型。1.3 贪心算法的基础思考方式贪心的核心就一句话不做全局规划只看当前这一步选一个局部最优的决策希望它能导出全局最优。听起来像废话但在区间问题上贪心之所以成立是因为区间之间有种“排序后序贯决策”的特殊结构。你按某个端点排序后每次只需要关心当前状态的一个边界值不需要回头看已经处理完的区间。学习区间问题最好的方式是先理解贪心策略的“直觉”再用反证法或者替换法说服自己最后写代码验证。千万不要只会背代码遇到变式照样会翻车。2. 区间选点最少点覆盖所有区间2.1 问题定义与最朴素的直觉给定N个闭区间[l_i, r_i]在数轴上放若干个点要求每个区间内至少有一个点求点的最少数量。最朴素的想法是从左往右扫描遇到一个还没被覆盖的区间就在它的某个位置放一个点。问题是放在哪里直觉告诉你应该放在“尽量靠右”的位置因为越靠右越有可能顺便覆盖后面的区间。那么什么叫“尽量靠右”最靠右的位置就是当前区间的右端点。所以贪心策略出来了把所有区间按右端点从小到大排序依次扫描。如果当前区间的左端点大于上一个选择的点的位置说明上一个点覆盖不到它就选择当前区间的右端点作为新点。2.2 贪心策略按右端点排序为什么要按右端点排序而不是按左端点排序这里有一个很经典的反例区间1: [1, 10] 区间2: [2, 3]如果按左端点排序先处理[1,10]在右端点10放一个点然后区间[2,3]已经被覆盖结果用了1个点。但这样其实“浪费了”放点的位置。我们再看一组区间A: [1, 5] 区间B: [2, 6] 区间C: [3, 4]如果按左端点排序选右端点第一个右端点是5覆盖了A和BC还没覆盖所以再选C的右端点4一共2个点。但如果按右端点排序第一个右端点是4C然后A和B都包含4吗A包含B不包含所以B需要再选一个点6共2个点。好像一样。真正能体现右端点排序优势的是更长的例子[1, 2] [3, 5] [4, 6] [7, 9]按左端点排序第一个右端点2覆盖[1,2]下一个[3,5]左端点32选右端点5覆盖[3,5]和[4,6]下一个[7,9]左端点75选右端点9。共3个点。 按右端点排序[1,2]右端点2覆盖它[3,5]右端点5选点5同时覆盖[4,6][7,9]选点9。也是3个点好像结果一样。其实这两个策略在很多常规数据下结果相同但右端点排序有严格的正确性保证而左端点排序在某些特殊构造下会出错。我记得有一个经典反例[1, 3] [2, 5] [4, 6]左端点排序第一个右端点3覆盖[1,3]和[2,5][4,6]左端点43选右端点6。共2个点。 右端点排序第一个右端点3覆盖[1,3]和[2,5][2,5]包含3覆盖[4,6]不包含3选6。共2个点结果一样。看起来左端点排序在这个例子里也没问题但左端点排序在这个方向上不存在严格证明。网上很多资料直接用“按右端点排序”因为它有替换法证明而左端点排序只能碰运气。实际写代码时按右端点排序才是最稳妥的选择。2.3 正确性证明思路这个证明可以用替换法。假设贪心算法选出的点集是G {g1, g2, ..., gk}最优解的点集是O {o1, o2, ..., om}其中m是最少点数。我们要证明k m。关键在于证明贪心选择的每个点的位置都不比最优解对应顺序中的点更靠左。具体地第一个贪心点g1一定是右端点最小的那个区间的右端点而最优解中覆盖这个区间的点o1不可能比g1更靠右因为是覆盖该区间的最优解该点必须落在区间内而该区间右端点最小所以o1 ≤ g1也就是g1不会比o1更靠左。然后用归纳法处理完第i个点时贪心选择的点位置g_i不早于最优解中对应的o_i。既然贪心点不落后那么贪心选完第i个点后剩余待覆盖的区间集合不会比最优解处理完第i个点后更多。所以贪心不会比最优解使用更多点。反过来最优解是最少的所以两者相等。这个证明思路很重要因为后面最大不相交区间数量、区间覆盖也会用到类似的替换法。2.4 C代码实现与踩坑点直接看代码#include iostream #include algorithm using namespace std; const int N 100010; struct Range { int l, r; bool operator (const Range W) const { return r W.r; } } range[N]; int main() { int n; scanf(%d, n); for (int i 0; i n; i) scanf(%d%d, range[i].l, range[i].r); sort(range, range n); int cnt 0; int last -2e9; for (int i 0; i n; i) { if (range[i].l last) { cnt; last range[i].r; } } printf(%d\n, cnt); return 0; }有几个细节容易踩坑last初始值要设成一个极小数比如-2e9不能设0因为区间端点可能是负数。判断条件是range[i].l last不是。因为两个闭区间如果只在端点相碰点放在端点上可以同时覆盖两个区间。比如[1,2]和[2,5]在2放一个点就都覆盖了。如果你用会认为[2,5]没被覆盖结果多放一个点WA。如果区间是左闭右开的[l, r)判断条件要改成range[i].l last因为此时端点处不算覆盖。做题时先看清楚题目说的是闭区间还是开区间人家挖的坑就在这。2.5 示例数据手工推导我准备一组样例5 1 3 2 5 3 6 4 7 6 8按右端点排序后是[1,3] [2,5] [3,6] [4,7] [6,8]初始last -∞第一个区间[1,3]1 -∞放点3last 3。[2,5]2 3不成立所以跳过。[3,6]3 3不成立跳过。注意区间[3,6]包含点3所以确实不用新点。[4,7]4 3放点7last 7。[6,8]6 7不成立跳过。答案是2个点分别是3和7。手工推一遍就能理解为什么判断条件是严格大于。3. 最大不相交区间数量边贪心边证明3.1 问题背景与贪心策略给定N个区间选出尽可能多的区间使它们两两不重叠端点重合视情况一般算作不相交。这个问题的贪心策略和区间选点一模一样按右端点排序然后从左到右扫描。如果当前区间的左端点大于等于上一个选中区间的右端点就选择当前区间并更新右端点为当前区间的右端点。这个策略的直觉是为了给后面的区间留出更多空间我们应该选择结束时间更早的区间。就像一个人一天要赶很多场活动每一场都选最早结束的那个就能参加最多的场次。3.2 为什么与区间选点是“孪生兄弟”如果你已经写过区间选点的代码你会发现最大不相交区间数量的代码几乎一模一样只是比较条件从l last换成了l last因为要保证两个闭区间没有公共点。这不是巧合这两个问题在数学上是对偶的。区间选点要求用最少的点打中所有区间而最大不相交区间要求选出最多互不重叠的区间。你选出的每一个点都可以对应一组被它覆盖的、互不重叠的、在数轴上从左到右排列的区间。反过来一组互不重叠的区间每个区间至少需要一个不同的点来覆盖。所以最少点数 最大不相交区间数量。很多教材里会专门讲这个等价关系理解了它两道题能同时记住。3.3 代码实现#include iostream #include algorithm using namespace std; const int N 100010; struct Range { int l, r; bool operator (const Range W) const { return r W.r; } } range[N]; int main() { int n; scanf(%d, n); for (int i 0; i n; i) scanf(%d%d, range[i].l, range[i].r); sort(range, range n); int cnt 0; int last -2e9; for (int i 0; i n; i) { if (range[i].l last) { cnt; last range[i].r; } } printf(%d\n, cnt); return 0; }3.4 端点相撞到底算不算重合这里有一个非常容易在面试里被追问的点如果两个区间是[1,2]和[2,3]它们算不算不相交在数学的闭区间定义里它们确实有一个公共点2所以是“相交”的。但在算法题约定里很多题目会规定“端点重合不算相交”或者“区间之间可以有公共端点”。这类题目你必须在开头就假设好比较时用l last允许端点重合还是l last不允许端点重合。如果题目说“区间之间不能有公共点”那就用。如果题目说“端点重合不影响”那就用。纯靠记忆不行要能根据题目描述现场判断。实测中大部分区间问题的经典模板默认端点重合不算冲突也就是用所以初学时按这个来就行但做题时还是要看题目要求。补充一个例子验证一下贪心选择确实是正确的4 [1, 2] [2, 3] [3, 4] [1, 3]按右端点排序后是[1,2]、[2,3]、[3,4]、[1,3]排序时[1,3]右端点3要放在[3,4]前面所以顺序是[1,2]、[2,3]、[1,3]、[3,4]。扫描过程选[1,2]last 2。[2,3]2 2成立选它last 3。[1,3]1 3不成立跳过。[3,4]3 3成立选它last 4。答案是3。你可以自己试试是不是没有其他方案能选到4个区间这就是贪心给出的最优解。4. 区间分组让互不相交的区间待在一起4.1 问题和贪心策略区间分组是这四道题里“画风”最不一样的一道。它的目标是把所有区间分成最少的若干组每组内的区间两两互不相交。举个例子假设有5个区间[1, 3] [2, 4] [3, 5] [4, 6] [5, 7]这几个区间每个都和相邻的重叠肉眼可见至少需要3组[1,3][3,5][5,7]端点重合视为不相交是一组[2,4][4,6]是一组但[2,4]和[3,5]有重叠所以要另起一组看起来正好3组能装下。贪心策略按左端点从大到小排序其实就是升序扫描每个区间尝试把它放进某个已有的组。关键问题是怎么知道它能放进哪个组答案是维护每个组当前最后一个区间的右端点。如果当前区间的左端点大于某个组的最后右端点说明它和这个组最后一个区间不相交可以放进这个组。由于我们只需要判断“有没有一个组能放下”而不是具体哪个组所以用小根堆维护所有组的右端点取最小的那个看能不能放。4.2 小根堆维护每个组的右端点为什么只要看最小右端点的组因为贪心策略下所有组的右端点都可以看成“最紧张的那个状态”。如果当前区间的左端点比最小的右端点还小说明它和每个组都有重叠那必然要新开一组。如果它大于等于最小右端点那至少和右端点最小的那个组不重叠直接放进那个组即可。注意这里比较的是heap.top() range[i].l还是heap.top() range[i].l取决于“端点重合是否允许放同一组”。经典模板默认允许端点在同一个点上也就是heap.top() range[i].l时放入否则新开组。如果你遇到题目说左右端点不能相碰就改成heap.top() range[i].l。这个“看最小右端点”的思路特别像在窗口排队每队最后一个人办完业务的时间最早结束的队伍最空新来的人只要比那个时间晚到就能排到那一队。4.3 正确性证明思路这个证明常用反证法。假设贪心算法在第i步不得不开新组而最优解此时不需要开新组也就是说当前区间与最优解中每组最后一个区间都不相交。但贪心选择的是所有组里右端点最小的那个如果当前区间与这个最小的有重叠那它与所有组的最后一个区间都有重叠因为其他组的右端点更大矛盾。这正是“鸽巢原理”式的论证如果重叠度足够高你不可能不新开一组。从另一个角度说区间分组的最少组数实际上等于数轴上某个时刻最多有多少个重叠区间同时存在。因为重叠在同一时刻的区间必须分到不同组所以组数至少等于重叠的最大深度而按左端点排序扫描时贪心恰好能构造出这个最大深度那么多个组。这两个观点殊途同归。4.4 代码实现与边界#include iostream #include algorithm #include queue using namespace std; const int N 100010; struct Range { int l, r; bool operator (const Range W) const { return l W.l; } } range[N]; int main() { int n; scanf(%d, n); for (int i 0; i n; i) scanf(%d%d, range[i].l, range[i].r); sort(range, range n); priority_queueint, vectorint, greaterint heap; for (int i 0; i n; i) { auto t range[i]; if (!heap.empty() heap.top() t.l) { heap.pop(); heap.push(t.r); } else { heap.push(t.r); } } printf(%d\n, (int)heap.size()); return 0; }注意几个边界点priority_queue默认是大根堆要用greaterint让它变成小根堆。heap.top() t.l是判断可不可以放入如果堆顶等于当前左端点而且题目不允许端点重合要改成heap.top() t.l。如果新开了组直接push(t.r)组的数量最终等于堆的大小。每组内区间是按左端点递增处理的所以放进去时只需保存该组最新右端点。手工推刚才那组样例5 1 3 2 4 3 5 4 6 5 7按左端点排序后不变。前三个区间[1,3]、[2,4]、[3,5]第一个直接放一组堆为{3}第二个左端点2堆顶33 2不成立开新组堆为{3,4}第三个左端点3堆顶33 3不成立开新组堆为{3,4,5}。第四个[4,6]左端点4堆顶33 4成立弹出3压入6堆为{4,5,6}。第五个[5,7]左端点5堆顶44 5成立弹出4压入7堆为{5,6,7}。组数是3正确。4.5 换一种无堆解法差分数组区间分组的本质是求“最大重叠层数”这个结论可以换个角度理解把每个区间看成一条线段记录数轴上每个位置被多少个区间覆盖覆盖次数的最大值就是最少组数。因为同一时间重叠在一起的所有区间必须各占一组。那么可以用差分数组做。比如所有端点范围在1e6以内for (int i 0; i n; i) { diff[l]; diff[r]--; }然后前缀和求最大值。但注意闭区间端点的处理要小心如果区间在l处开始、r处结束覆盖位置是[l, r]我们可以在l处加1在r1处减1。但前提是坐标范围不大。这个方法的复杂度是O(坐标范围 n)在坐标范围大的时候不如排序堆的做法通用。所以竞赛里推荐用堆的方法差分数组适合当作一条思维扩展来理解。5. 区间覆盖用最少的区间拼出一条通路5.1 问题描述与贪心策略第四次变复杂了一点给定一个目标区间[s, t]以及N个可选区间要求从N个区间里选出尽可能少的区间使得这些区间的并集完全覆盖[s, t]。如果不能覆盖输出-1。贪心策略是把所有区间按左端点排序从左往右扫描每次从所有能覆盖当前起点start的区间中选择一个右端点最远的区间然后更新start为这个右端点。重复这个过程直到start t或者找不到可选区间。为什么选右端点最远的和区间选点选右端点的理由一样越往后延展越远越省区间数。把这个问题想成铺路你从位置start出发面前有一些砖头区间每块砖头必须盖住你脚下的位置才能用。在能用的一堆砖头里当然选最长的那块铺出去最远这样剩下的路最短。5.2 贪心过程详解实现上有一个很典型的双指针技巧我单独拆开讲。先排序所有区间按左端点升序排。维护一个指针i从头扫描。每一轮循环找所有l start的区间更新max_r max(max_r, r)。如果max_r start说明存在一段空隙没有任何区间能覆盖start直接返回-1。区间数加1把start max_r。如果start t结束。关键点第1步里的循环不能每次都从头开始因为之前的区间已经被处理过。用一个全局指针i每一轮从当前i开始向后扫凡是l start的都参与更新遇到第一个l start就停止进入下一轮。5.3 代码实现与断档处理#include iostream #include algorithm using namespace std; const int N 100010; struct Range { int l, r; bool operator (const Range W) const { return l W.l; } } range[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, range[i].l, range[i].r); sort(range, range n); int cnt 0; bool success false; int i 0; while (i n) { int max_r -2e9; while (i n range[i].l s) { max_r max(max_r, range[i].r); i; } if (max_r s) break; // 断档 cnt; if (max_r t) { success true; break; } s max_r; } if (!success) printf(-1\n); else printf(%d\n, cnt); return 0; }这里有个隐藏很深的bug内层while结束后i指向的是第一个l s的区间下一轮外层循环不会重复访问已经遍历过的区间这是正确的。但要注意当max_r t时break前必须把success置为true否则循环结束条件是i n时也可能误判为失败。5.4 手算示例假设[s,t] [1, 5]区间是4 [1, 2] [2, 4] [3, 6] [4, 5]排好序后直接扫描。第一轮start 1所有l 1的只有[1,2]max_r 2。cnt 1s更新为2。第二轮start 2所有l 2的有[2,4]max_r 4。cnt 2s 4。第三轮start 4所有l 4的有[3,6]和[4,5]max_r 6cnt 36 5成功。答案是3。当然如果区间[3,6]能直接覆盖到6那确实第2轮的时候就应该被选上为什么第二轮没有选它因为在第二轮开始时start 2而[3,6]的左端点3 2它覆盖不住当前位置2不能“抬脚”从2开始铺。这就是“必须覆盖当前起点”的约束。6. 四个问题的横向对比与思维工具6.1 一张表看懂四个策略问题名称排序方式扫描/更新规则关键数据结构区间选点按右端点升序l last时选点更新last为该区间右端点变量last最大不相交区间按右端点升序l last时选取更新last为该区间右端点变量last区间分组按左端点升序堆顶 l则放入该组否则开新组小根堆维护各组右端点区间覆盖按左端点升序每轮找所有l start区间取最大右端点更新start双指针 变量一眼看过去选点和最大不相交的排序键一样更新规则只差一个等号分组和覆盖都用左端点排序但分组用堆处理“并行容器”覆盖用双指针处理“串联推进”。这是它们最核心的区别。6.2 什么时候用右端点什么时候用左端点判断依据不是死记硬背而是看问题的时间方向。如果想让“让后面的区域更自由”你自然希望当前选中的区间结束得尽可能晚或早选点和最大不相交问题中核心矛盾是“一个点/区间和后面区间是否冲突”因此按右端点排序让最紧迫的区间先决策。分组和覆盖问题中核心矛盾是“起点固定能延伸多远”因此按左端点排序从左边开始逐步推进每一步贪心地延伸最远。用生活类比如果是在一天内安排活动优先选最早结束的右端点排序如果要铺一条路从左往右优先选能铺最远的那块“砖”左端点排序。这个直觉能帮你应对很多变式题。6.3 贪心的常见误区误区一贪心不证明直接写代码。区间题的正确性证明并不难熟练之后五分钟能写完但跳过的后果是遇到刁钻数据WA到怀疑人生。误区二端点等号搞错。闭区间和开区间、允许端点重合和不允许端点重合在四道题里分别对应不同的比较符号。一题之差可能就是WA。误区三区间覆盖里忘记更新起点或者死循环。双指针如果指针没有推进内层循环会无限跑。写完之后用随机数据对拍是排查这类问题的好方法。7. 实战中的细节与扩展7.1 输入输出与调试经验很多人觉得区间题代码短不需要调试其实这是个误区。我写区间题最容易出错的点有三个第一结构体运算符重载写错。如果从小到大排序operator里返回的是r W.r还是W.r r自己也容易绕进去。如果你不想重载可以这样写sort(range, range n, [](const Range a, const Range b) { return a.r b.r; });lambda表达式更直白不容易出错。第二last初始化用-2e9而不是0。很多题目坐标可以是负数用0会导致初始判断出错。第三区间覆盖里内层循环的i指针容易失控。建议每次更新max_r后先打印一次i、s、max_r确认指针没有跳过头。7.2 数据范围与复杂度的关系四个问题的时间复杂度都是O(n log n)主要瓶颈在排序。空间复杂度是O(n)。当n达到1e5或者1e6时这个复杂度完全没问题。但如果你用差分数组做区间分组复杂度会变成O(坐标范围 n)坐标范围小的时候更快但坐标范围1e9时就爆了所以竞赛里排序堆的做法更保险。还有一个值得注意的点区间选点和最大不相交区间数量在n很大而坐标范围很小的时候其实也可以转换成差分题不过意义不大。作为算法学习者优先掌握排序 贪心这套通法。7.3 类似变式带权区间调度、最少箭头戳破气球经典区间题的价值在于它可以变形出很多高级题。我自己遇到过的两个典型变式带权区间调度每个区间除了左右端点还有一个权重要选一组互不相交的区间使总权重最大。这个问题贪心解决不了因为局部“最早结束”不保证权重最大需要按右端点排序后用动态规划。转移方程很简单dp[i] max(dp[i-1], dp[p] w[i])其中p是第i个区间之前最后一个不与它重叠的区间下标二分查找优化到O(n log n)。最少箭头戳破气球LeetCode 452其实就是区间选点的换皮题。气球是区间箭头是点一支箭可以射穿多个重叠区间的公共位置求最少箭数。它和区间选点完全等价有些版本甚至不强调“选点”而是说“引爆气球”。遇到这种题你只要能认出区间模型代码几乎是模板级别的。还有一类“会议安排”变式给你一堆会议时间问最多能参加几个会议这就是最大不相交区间数量。而“最少会议室数量”则是区间分组。同一个生活场景换一个问法就是两套完全不同的问题本质都是区间贪心。8. 个人经验收尾这套区间问题我前前后后写过不下二十遍每次面试前还会重新手推一遍证明。我最大的体会是学区间题不能只记“按右端点排序”这个口诀而是要理解排序之后为什么扫描过程能得到全局最优。另外一个小技巧把四道题的代码模板整理到一个文件里只改排序键和判断条件每次写新题时对照“它到底是选点、选区间、分组还是覆盖”然后套模板再根据题目要求调整等号。这套流程熟练之后这类题基本是送分题。还有一个建议练习时不要只刷通过可以尝试用随机数据生成器对拍。比如自己写一个暴力DFS求最优解再和贪心跑出来的结果对比能帮你快速发现那些藏在角落里的反例。我之前就是靠对拍才发现区间覆盖里指针推进有问题。希望这篇总结能帮你在面试和竞赛里稳稳拿下区间题。如果后续你遇到某个区间问题的奇怪变式就用这篇文章里的“问题分类 贪心策略 证明 代码”四步法去拆解应该能少走不少弯路。