企业官网建设流程全解析

如果你和我一样按专题刷题，大概率会遇到一个现象：贪心这一章里，区间问题简直像开了单独的分区。区间选点、最大不相交区间数量、区间分组、区间覆盖，四道题长得都很像，都是给你一堆[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]：堆顶4，4 < 2不成立，说明所有组在2时刻都还在忙（唯一的组要到4才空），新开一组，push3，堆为{3, 4}。
• 处理[5,6]：堆顶3，3 < 5成立，说明[2,3]这组在5之前已经空闲，可以复用。弹出3，push6，堆变为{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_queue<int, vector<int>, greater<int>> 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 一张速查表

我后来把四道题的判别方式浓缩成一张表，刷题时用来对照，很少再混淆：

这张表我贴在自己笔记里，每次做题前先对着表找“类型”，再看具体细节。用熟之后会发现，很多变形题本质都是这四个模型的组合或包装。

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右端点，不需要额外定义比较器，用greater<int>就行。覆盖题如果不记录具体方案，也不需要自定义结构体比较器。

7.3 数据范围与时间复杂度意识

很多人学这四道题时只记了模板，没养成为复杂度把关的习惯。实际上，四个模型的标准解都是 O(n log n)，瓶颈在排序和堆操作。如果数据范围到了10^6甚至10^7，O(n log n) 依然可行，但要注意别在循环里反复申请priority_queue，那会引入大量内存分配开销。

我踩过的一个真实坑是：在一道覆盖题里，数据范围s和t达到10^9，候选区间n是10^5，我用数组下标做覆盖标记，直接越界崩溃。后来改成排序 + 双指针，瞬间跑过。所以结论是，当坐标范围远大于n时，不要试图模拟整个数轴，一定回到贪心扫描本身。

7.4 从“背模板”到“自己会选模板”的最后一公里

有段时间我对四个模板的代码已经滚瓜烂熟，但遇到某题还是容易套错。后来我找到的办法是：把四道题打乱顺序，每做一道新题都先强制自己写两行注释：

// 目标：最少点/最多区间/最少组/最少覆盖？ // 排序：r 还是 l？维护什么数据结构？

这两行写不出来，就不写代码。这个方法听起来很笨，但它逼着我把问题归类和算法选择变成显式思考，而不是靠“上一题做的是分组这题应该也差不多”的错觉。带过的几个低年级同学用这个办法练习两到三周后，正确率提升都很明显。

另外，关于这四道题的证明，我的体会是：把“为什么贪心这一步不会让后面的结果更差”想清楚，比记住反例重要得多。因为笔试不一定会考原题，但它一定考察你有没有真的理解贪心选择的“诱因”。比如覆盖题你的诱因是“右端点越远，覆盖推进越多”，这个理由在任何新的覆盖题里都成立，这比死记“左端点排序后双指针”能应对更多的变体。

最后再分享一个我很常用的自测组合：每次写完一段贪心代码，我都会立刻构造三组数据。第一组所有区间都互不相交，第二组所有区间完全重叠，第三组一个区间包住其他所有区间。如果三组数据都能得到直觉上正确的答案，才提交。这三组数据不复杂，但能击穿绝大多数排序方向、端点符号和初始化错误。尤其是“一个包全部”的数据，对覆盖题和分组题特别有用，因为它能直接暴露推进变量是否被错误更新。养成这个自测习惯之后，我的区间题提交一次过率提高了不少。