1. 一道让很多新手栽跟头的“简单题”先看题目信息学奥赛一本通1324【例6.6】整数区间题目大意是这样的给定 n 个闭区间每个区间用 [ai, bi] 表示ai、bi 都是整数现在要求你选出尽量少的整数点使得每个区间里至少包含一个被选中的点。换句话说你要找一个整数点的集合让集合与每个区间的交集都不为空并且让这个集合的规模最小。输出最少需要选几个点。样例是这样的输入 4 3 6 2 4 0 2 4 7 输出 2我第一次看到这道题的时候脑子里蹦出来的想法是这还不简单把所有区间的公共交集找出来选一个点就完事了。但实际一算就知道不行因为这些区间不一定有公共交集而且就算有也只能覆盖一部分区间。后来我想到了贪心但最开始拍脑袋“按左端点排序每次都选区间左端点”结果连样例都过不了。这道题就是这么个调性看着简单实际上对“贪心策略的选择”要求很高你不把原理想透十有八九要翻车。这篇博文就是把这题的完整思路、贪心证明、代码实现、常见踩坑全部拆开适合正在刷《信息学奥赛一本通》的OI选手、准备算法比赛的初学者还有那些学贪心学得“会做但不会证明”的朋友。看完你不仅会 AC 这一题还能顺手把同类区间贪心问题全部吃透。2. 核心思路拆解为什么必然是该贪心策略讲代码之前我必须先把思路掰开揉碎。因为这题的难点不在代码而在“为什么这样做是对的”。你要是只会背代码换个类似的题照样不会。2.1 从朴素想法到贪心选择先把问题翻译成大白话有 n 个线段每个线段是一段整数范围你要在一些整数位置上“站岗”要求每条线段上至少有一个岗哨求岗哨数量的最小值。一个很自然的想法是既然要覆盖所有区间那尽量让每一个选出来的点同时覆盖尽可能多的区间。这个思路本身没问题问题在于“怎么选才能覆盖最多”。如果按左端点从小到大排序然后从左往右看区间选择一个点让它在当前区间内同时尽量靠右这样它就能覆盖更多右边的区间。关键点是“尽量靠右”也就是当你决定在某一段区间里选点时直接选这个区间的右端点。为什么因为右端点是整个区间里最靠右的位置选了它左边已经覆盖的不受影响右边还没处理的区间被覆盖的可能性最大。但这里有个更深的问题排序时到底按左端点还是右端点排这决定了整个算法的走向。如果按左端点排序从左往右扫描时每次遇到一个新区间如果它和当前已经选取的最后一个点没有交集就需要新选一个点。为了保证新点能覆盖尽可能多的后续区间你会把新点放在当前新区间的右端点。这个逻辑顺下来其实也说得通但实现起来有一个很隐蔽的缺陷后面我会详细讲。而按右端点排序是另一个更经典的思路每次选择当前所有未覆盖区间里右端点最小的那个选择它的右端点。两种思路看起来差不多但实际效果完全不同。我个人推荐按左端点排序然后选右端点这个写法因为它在脑内模拟和代码实现上都更直观也不容易出错。但注意虽然排序键是左端点真正的“选点动作”一定发生在右端点上这是整道题的核心。2.2 为什么不是按左端点排序就完事很多初学者包括当年的我会写出这样的流程按左端点从小到大排序。记录一个当前点 pos初始设为第一个区间的右端点。遍历后面的区间如果当前区间的左端点 pos说明 pos 覆盖不到它于是 pos 当前区间的右端点答案加一。如果当前区间的左端点 pos说明它已经被 pos 覆盖直接跳过。你看这个流程里排序确实按左端点但 pos 的更新是取右端点。这个写法的问题是你无法保证“当前区间的右端点”一定比 pos 大。试想一种情况当前区间完全被 pos 覆盖比如 pos 5当前区间是 [3, 4]它的左端点 3 小于 5于是你判断它被覆盖了直接跳过这没问题。但如果当前区间是 [6, 6]左端点大于 pos于是你更新 pos 6答案加一这也没问题。问题出在另一种情况当前区间的左端点 pos但它的右端点也比 pos 小也就是整个区间在 pos 的左边。这种情况会出现在排序不稳定的时候吗如果你按左端点排序且当前区间左端点 pos但右端点 pos说明这个区间完全在 pos 的左边那它怎么会被标记为覆盖答案是它不会被 pos 覆盖。比如第一个区间是 [10, 20]pos 20。第二个区间是 [1, 2]按左端点排序它应该排在前面所以顺序不会反过来。但如果存在几个左端点相同的区间比如 [5, 10] 和 [5, 6]排序后可能 [5, 6] 在当前而 pos 被之前的某个大区间更新为 7那 [5, 6] 就会被误判为覆盖实际上并没有。这就是按左端点排序后单纯判断左端点的缺陷。那有没有解决办法有判断条件用“当前区间的右端点 pos”就说明真的覆盖不到而不仅仅看左端点。但这样代码就绕了一层思维负担变大。反观按右端点排序的经典做法每一步都逻辑干净。2.3 贪心正确性的非正式证明这里的贪心策略用大白话讲就是把所有区间按右端点从小到大排序每次取当前最靠左结束的区间取它的右端点作为选点然后去掉所有被这个点覆盖的区间重复直到所有区间都被处理。为什么这是对的我给一个直观论证。假设当前未处理区间里存在一个右端点最小的区间 R。任何合法的答案至少要在 R 里选一个点否则 R 没被覆盖。既然必须选一个点那选 R 的右端点 r 绝不比选 R 里其他点差因为 r 是最靠右的位置它能覆盖的从当前时刻开始往右看的区间不少于 R 内任何其他点能覆盖的区间。于是你总能构造出一个最优解它在处理 R 时选的是右端点 r。既然存在“选 r”的最优解那贪心选择 r 就不会导致失去最优解后面的问题变成了一个规模更小的同构子问题。这就是贪心选择性质和最优子结构。再换个说法你选一个点本质上是给所有区间划了一条“覆盖线”。如果你选的点可以往右挪那它只会多覆盖区间不会少覆盖区间。所以每次必须选择点时往右挪到头也就是右端点是最赚的。而为什么按右端点排序因为右端点最小的区间是最“着急”的区间它最早结束过了它的右端点就永远没机会再覆盖它了。处理问题时要先处理最紧迫的约束这个思想在贪心、动态规划、调度问题里都特别常见。我建议你把上面这个“可右移”论证写在草稿纸上用自己的话推一遍。面试或者笔试里这题的变种经常出现能讲清楚证明和只会 AC 是完全不同的层次。3. 代码实现与关键细节思路理清楚之后写代码就是水到渠成的事。这里我给出一个完整的 AC 代码按左端点排序、取右端点贪心的写法稳定且易读。3.1 参考代码C#include bits/stdc.h using namespace std; struct Interval { int l, r; }; bool cmp(const Interval a, const Interval b) { if (a.l ! b.l) return a.l b.l; return a.r b.r; } int main() { int n; cin n; vectorInterval seg(n); for (int i 0; i n; i) { cin seg[i].l seg[i].r; } sort(seg.begin(), seg.end(), cmp); int ans 1; // 至少要选第一个区间的右端点 int pos seg[0].r; // 当前选中的点 for (int i 1; i n; i) { if (seg[i].l pos) { // 当前区间覆盖不到 pos必须在这个区间里新选一个点 ans; pos seg[i].r; } else if (seg[i].r pos) { // 当前区间完全在 pos 的左边说明之前选的点太靠右 // 这时把 pos 拉回来但不增加答案数量 pos seg[i].r; } } cout ans endl; return 0; }这个代码我已经用样例验证过输出 2。这里我默认大家用的是新版 Dev-C 或者 VS Code 配的编译器C11 及以上标准bits/stdc.h在比赛环境里一般都能直接用但在某些严格环境比如部分在线评测系统的老版本编译器可能不支持改成#include vector、#include algorithm、#include iostream也行。3.2 代码里的几个关键细节第一个细节ans初始值为什么是 1 而不是 0因为排序后的第一个区间无论如何都要被覆盖你在它的右端点先放一个点这是必然的开局。如果你从 0 开始逻辑上循环里第一次遇到区间就会加一也能得到同样的结果但那样代码要多写一层判断而且容易把第一个区间漏掉。第二个细节else if (seg[i].r pos)这个分支很多人会漏。如果你不处理这个分支那么当遇到一个完全在当前选中点左侧的区间按左端点排序后这种区间可能出现在 pos 被更新到很大之后它会被错误地当成“已经被覆盖”。但实际上它的右端点小于 pos左端点也小于 pospos 根本不在它的范围内。这时把 pos 拉回seg[i].r是最优的因为你没必要继续用一个更靠右的点来覆盖它直接选它的右端点即可并且答案不增加。第三个细节排序比较函数里左端点相同的情况按右端点升序。如果你在cmp里只比较左端点可能因为排序不稳定导致顺序不确定进而影响pos的更新顺序。虽然大多数情况下结果不会错但规范写法还是把右端点也纳入比较省得出现玄学问题。3.3 关于数据范围与输入输出的建议《信息学奥赛一本通》的题目数据范围一般不会太刁钻但做竞赛题时多留个心眼总没错。我查了一下这道题的约束条件 n 一般不超过几千或一万的量级也就是说 O(n log n) 的排序完全够用O(n^2) 暴力在极端数据下会超时所以排序贪心是正解。输入输出方面如果 n 比较大建议用scanf/printf代替cin/cout。在刷题时cin没关同步ios::sync_with_stdio(false)的情况下可能比scanf慢不少。我在代码里为了演示用了cin你在实际提交时可以加上ios::sync_with_stdio(false); cin.tie(nullptr);这两行能显著提升cin的速度。如果你用scanf代码改成scanf(%d, n); for (int i 0; i n; i) { scanf(%d%d, seg[i].l, seg[i].r); } printf(%d\n, ans);我个人建议新手直接用cin 关同步代码可读性好性能也够。至于用printf需要注意%d对应int不要写成%lld。4. 常见错误排查与避坑指南这题我在教学和刷题过程中见过各种奇奇怪怪的错法这里统一整理成一个速查表顺手把背后的原因写清楚方便你对照自查。错误类型错误表现原因分析正确做法按左端点排序但没处理 pos 回退输出比正确答案偏大或偏小新区间完全在 pos 左侧时被误判为已覆盖增加seg[i].r pos分支回退 pos按右端点排序但每次选左端点输出偏大选的左端点不够靠右覆盖范围变小每次取当前区间的右端点计数初始化为 0某些情况下输出少 1第一个区间没有被任何点覆盖时答案少算从 1 开始或循环内统一判断比较函数只比较 l 没比较 r排序顺序不稳定排序算法不稳定或比较不严格cmp里先比 l再比 r判断条件写成与混淆边界区间被跳过闭区间包含端点左端点等于 pos 时其实已被覆盖用判断覆盖不到默认区间端点不保证有序交换 l 和 r 后结果错题目输入可能给的是乱序端点读入时如果 l r 就 swap4.1 错误一按左端点排序但忽略区间完全在 pos 左边这是一个特别容易踩的隐坑。我举个例子区间是 [1, 2]、[6, 8]、[3, 4]排序后是 [1, 2]、[3, 4]、[6, 8]。按我们的算法pos 初始为 2然后遍历 [3, 4]左端点 3 2所以新增一个点 pos 4答案变为 2。再遍历 [6, 8]左端点 6 4再新增 pos 8答案变为 3。没问题。但如果排序后的区间是 [1, 10]、[5, 6]、[7, 8]pos 初始为 10遇到 [5, 6]它左端点 5 10如果不处理 r pos 分支判断为已覆盖跳过。遇到 [7, 8]同样判断为已覆盖跳过。最后答案 1。但真的选 1 个点就能覆盖这三个区间吗选 10 的话[5, 6] 覆盖不到[7, 8] 也覆盖不到。所以正确答案是 2 或者 3。这就是我代码里else if (seg[i].r pos)分支存在的意义。每次遇到这样完全“缩在左边”的区间就把 pos 拉回去因为反正答案不增加与其用一个右边的大点不如用一个左边更精准的点。4.2 错误二按右端点排序时选了左端点这种做法很容易出现在“我理解思路但写代码手滑”的瞬间。你按右端点排好序后第一个区间是右端点最小的选它的左端点作为 pos。后面遇到覆盖不到的区间你还是选它左端点。你会发现答案可能对了也可能不对全看右端点排序和左端点选点的组合是否巧合地产生最优解。但更多时候答案会偏大。因为你选的点不够靠右覆盖的区间数量少了。一定要记住右端点排序之后选点是选右端点。而左端点排序的写法里选点是选当前区间的右端点。不论哪种写法动手选的那个点都是当前区间的右端点。4.3 错误三边界是闭区间判断时搞错等号题目说的是闭区间也就是端点本身也算在区间内。所以如果 pos 5区间是 [5, 8]那么 pos 已经在区间里不需要新增点。判断覆盖不到的条件是seg[i].l pos也就是说左端点严格大于 pos 才覆盖不到。如果你写成那么 pos 5区间 [5, 8] 也会被要求新增点答案偏大。这个细节在写代码时特别容易看走眼样例数据不一定能测出来但大数据一上就容易出问题。4.4 错误四排序比较函数写错C 的sort需要严格弱序的比较函数。如果你只写return a.l b.l那么当两个区间左端点相等时排序顺序未定义可能会交换位置。多数情况下这不会影响最终答案但存在特例。我见过有人在cmp里写成return a.l b.l这会导致排序算法在判断相等时返回 true严格弱序被破坏sort 可能运行时的行为就诡异了甚至直接 RE。正确的写法就是先比左端点左端点一样再比右端点。4.5 一个暴力对拍的辅助方法如果你不确定自己的贪心写法对不对我教你一个笨办法写一个暴力枚举的验证代码随机生成小数据穷举所有可能的选点组合找出真正的最小值然后跟你的贪心答案对比。数据量小的时候比如 n 10坐标范围 0~20暴力搜索完全可行。这一步虽然不在竞赛提交的范围内但对于理解题目和验证思路极有帮助。我自己刷题时候会专门准备一个brute.cpp框架来对拍。几分钟就能写完却能省下后面调试的几小时。这里不展开暴力代码了但建议你一定要自己敲一遍。5. 从整数区间到更广的贪心问题这道题的思路可以顺藤摸瓜延伸出好几类常见题型你在《信息学奥赛一本通》或者其他刷题网站上都会反复碰到。5.1 同一模型的经典变式第一个变式是最多不重叠区间个数。给你 n 个区间问最多能选出多少个互不重叠的区间。这个题和整数区间是孪生兄弟贪心策略是按右端点排序然后依次选择右端点最小且不与上一个已选区间接界的区间。代码结构和整数区间几乎一模一样区别只是统计逻辑。第二个变式是给定一个目标区间 [s, t]让你用最少的给定区间把它覆盖。这个题贪心策略是按左端点排序每次选择覆盖当前起点且右端点最远的区间然后更新起点。它跟整数区间的区别在于“选点”变成了“选段”但核心思想仍然是每次选择能覆盖最远范围的选项。第三个变式是区间分组问题比如有若干个课程每个课程有开始时间和结束时间问至少需要多少个教室。这种题可以用贪心加最小堆解决本质上也是区间调度家族的成员。你在学完这道整数区间后可以顺手把这些变式都做一遍效果比单纯刷十道不相关的题好得多。5.2 和《一本通》系列其他题目的关联《信息学奥赛一本通》的题目编排是循序渐进的贪心章节里出现的区间问题一般会从简单选点、区间覆盖再到更复杂的模型逐步深入。做到 1324 这一题时你应该已经掌握了排序、结构体、STL 的基本使用这道题就是一个综合应用的练习。它后面还会出现和图论有关的题目比如热词里提到的弗洛伊德算法那是求全源最短路径的经典算法和贪心思路不同但都属于“算法竞赛常见的思考模式”。我建议你每学一种新算法就回头把之前类似思想的老题重新做一遍对比它们的异同这样知识才会真正串联起来。我自己刷题时有一个习惯每做完一道经典题会在题号后面写三个东西——用的算法、排序的键、贪心取舍的核心逻辑。比如这题就写“贪心按左端点排序取右端点遇到 r pos 要回退”。下次复习时扫一眼这行笔记几秒钟就能把整道题捡起来。5.3 训练贪心的实用建议很多 OI 选手学贪心最大的困惑是我 AC 了这题但换个题还是不会。这很正常贪心本来就不是靠题海战术能速成的你需要的是“证明意识”。每次写完一道贪心题强迫自己回答两个问题为什么这个局部最优选择不会影响后续的全局最优如果我在这一步换一个看似更差的选择会不会反而更好如果你能清晰地答出这两个问题说明你真正掌握了这题而不是背了个套路。再分享一个具体的训练方法把一道区间贪心题的所有排序方式按 l 升序、按 l 降序、按 r 升序、按 r 降序都试一遍然后自己构造反例去推翻每一种错误的排序方式。这个方法非常费时间但效果极其显著。做完之后你会对“为什么这题只能这么排序”产生肌肉记忆而不是仅仅停留在看懂博客的层面。刷题时我建议给自己限定时间简单贪心题 15 分钟中等题 30 分钟超时就看题解。看题解不是丢人的事但要带着问题看它跟我卡住的点差在哪它的证明哪里是我没想到的看完之后合上题解从头把代码默写一遍。这样练个二三十道题你的贪心直觉就会明显上一个台阶。