刷算法题这几年，最怕看到两类题：一类是动态规划，状态转移方程搞死人；另一类就是贪心，思路看着挺对，一提交就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和B，C还没覆盖，所以再选C的右端点4，一共2个点。但如果按右端点排序，第一个右端点是4（C），然后A和B都包含4吗？A包含，B不包含，所以B需要再选一个点6，共2个点。好像一样。
真正能体现右端点排序优势的是更长的例子：
[1, 2] [3, 5] [4, 6] [7, 9]按左端点排序：第一个右端点2，覆盖[1,2]，下一个[3,5]左端点3>2，选右端点5，覆盖[3,5]和[4,6]，下一个[7,9]左端点7>5，选右端点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]左端点4>3，选右端点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 > -∞，放点3，last = 3。 [2,5]，2 > 3？不成立，所以跳过。[3,6]，3 > 3？不成立，跳过。注意区间[3,6]包含点3，所以确实不用新点。[4,7]，4 > 3，放点7，last = 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_queue<int, vector<int>, greater<int>> 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默认是大根堆，要用greater<int>让它变成小根堆。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，堆顶3，3 < 2不成立，开新组，堆为{3,4}；第三个左端点3，堆顶3，3 < 3不成立，开新组，堆为{3,4,5}。第四个[4,6]左端点4，堆顶3，3 < 4成立，弹出3，压入6，堆为{4,5,6}。第五个[5,7]左端点5，堆顶4，4 < 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，在r+1处减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 = 1，s更新为2。第二轮start = 2，所有l <= 2的有[2,4]，max_r = 4。cnt = 2，s = 4。第三轮start = 4，所有l <= 4的有[3,6]和[4,5]，max_r = 6，cnt = 3，6 >= 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求最优解，再和贪心跑出来的结果对比，能帮你快速发现那些藏在角落里的反例。我之前就是靠对拍，才发现区间覆盖里指针推进有问题。
希望这篇总结能帮你在面试和竞赛里稳稳拿下区间题。如果后续你遇到某个区间问题的奇怪变式，就用这篇文章里的“问题分类 + 贪心策略 + 证明 + 代码”四步法去拆解，应该能少走不少弯路。
