★ FEATURED ARTICLE 1. 为什么一道“看起来两分钟能做出来”的题提交时却总有人卡住我带信息学奥赛集训队的时候每次讲到《信息学奥赛一本通》1324这道题台下总有学生不以为然地说“这不就是排个序就完了吗”然后自信满满地交一发WA得莫名其妙。这道题目编号是1324标题叫【例6.6】整数区间放在贪心算法的例题里本身就是用来立规矩的你光知道“排序”不够还得知道按谁排、排完了怎么扫、边界条件要不要取等号。这几个细节没想透代码写得越快错得越稳定。题意其实特别短输入 n 个整数区间比如 [3,6]、[2,4]、[0,2]、[4,7]现在要选出尽量少的整数点使得每一个区间内都至少包含一个选出的点。最后输出最少需要几个点。样例里四个区间答案是 2选 2 和 6 可以选 2 和 4 也可以数量都是 2。也就是说这道题要的不是“唯一解”而是“最少点数的方案是否存在、怎么构造”。这个问题在算法里有个专门的名字叫“区间选点”属于典型的贪心模型。可很多人在初学时会把它理解成“求所有区间的公共交集”或者“把能合并的区间都合并了最后数一数有几段”。这两种理解离正确做法都很远。我记得有一次课上我让学生先自己写收上来的代码五花八门有人按左端点从大到小排有人用二维数组硬模拟还有人一边读入一边暴力枚举每个点覆盖了多少区间。只有真正理解了“每个区间都必须被摸到”这个约束才会发现排序策略里藏着题眼。所以这篇不打算只贴代码。我会从题意辨析开始讲清楚为什么按右端点排序是唯一的正解为什么中途的判断条件必须写成而不是再带你走一遍样例、看几个常见的错法。把这些东西搞明白你再去做“雷达覆盖”“活动安排”“POJ 1716”那一串区间贪心题都会觉得顺很多。2. 先把题意翻译清楚是“点覆盖区间”不是“区间交集”先别急着写代码拿支笔在草稿纸上画数轴。区间 [0,2] 和 [4,7]中间隔着一大段空档显然至少要选两个点一个放在 [0,2] 里一个放在 [4,7] 里。这个时候如果你去求所有区间的交集会发现交集是空的那么按“交集里放一个点就能覆盖全部区间”的思路来算答案就是 0 甚至根本没法放这显然不对。所以这道题不是求交集。再看一种容易混淆的情形区间 [0,5]、[2,6] 和 [3,4]。这三个区间的交集是 [3,4]所以在 [3,4] 里放一个点比如 4三个区间全部覆盖答案 1。这时候“求交集”碰巧有效于是有人就开始觉得“是不是把区间合并成若干段每段取一个点就行了”。注意这只是表面现象。如果区间变成 [1,2]、[2,3]、[3,4]合并之后是连成一条线的 [1,4]但一个整数点根本不可能同时落在 [1,2] 和 [3,4] 里因为 [2,3] 虽然把两端“连”起来了但2,3区间内的点不可能同时覆盖两端的区间——点 2 覆盖 [1,2] 和 [2,3]但够不到 [3,4]点 3 覆盖 [2,3] 和 [3,4]但够不到 [1,2]。所以这组区间需要两个点。区间合并算法会把它们看成一段直接输出 1这就错了。也就是说“区间之间有没有公共点”和“一个点能不能覆盖一串区间”是两件事。这道题要找的是一堆区间的“公共交点集合”的最少点数。一个点放在哪里它就能覆盖所有“包含这个点”的区间。我们的任务是在数轴上选择尽量少的坐标让每条区间至少被其中某个坐标“命中”。我上课的时候喜欢打个比方你管理着 n 条巡逻路段每条路段至少要安排一名保安站岗而且保安只能站在整数坐标的位置上。一个保安站在 x 点他就能负责所有包含 x 的路段。保安工资很贵所以你要用最少的人覆盖所有路段。这个比方听起来简单但请注意一个保安负责多少路段取决于他站的“位置”是不是落在那些路段的范围内而不是他所在的“路段”跟谁的编号连在一起。这个“位置”思维一旦建立起来贪心策略就顺理成章了。再补充一个容易忽略的细节区间是闭区间也就是包含左右端点。样例里 [0,2] 和 [2,4] 只需要在 2 这个点放一个保安就能同时覆盖两个区间因为 2 既属于 [0,2] 的右端点也属于 [2,4] 的左端点。一旦你把闭区间看成开区间或者在判断时用错了等号答案就会莫名其妙多 1。这一处差一个和的区别几乎是所有WA的源头。3. 贪心策略详解按右端点排序是这道题的“题眼”3.1 标准做法只需要五步这道题的正解非常简洁我建议所有学生都按下面这套流程走读入 n 个区间用结构体存每个区间的左端点 l 和右端点 r。把区间按右端点从小到大排序。先取排序后第一个区间的右端点当作放置的第一个点记录到last答案ans初始化为 1。从第二个区间开始往后扫如果当前区间的左端点l大于last说明之前放的点覆盖不到它于是在当前区间的右端点处放一个新点ans更新last为当前区间的右端点。如果当前区间的左端点l小于等于last说明last这个点已经落在了当前区间里直接跳过不用放新点。为什么第一步要取排序后第一个区间的右端点因为按右端点从小到大排序后第一个区间是所有区间里“最急着结束”的它的右端点最小。为了保证这个区间一定被覆盖必须在它内部放一个点。那这个点放在哪里最好放在它的右端点 R 上因为其他所有区间的右端点都大于等于 R——这是排序保证的——只要某个区间的左端点小于等于 RR 就落在那个区间里。换句话说R 是当前情况下“最能顺带覆盖其他区间”的位置。放着这么个位置不用反而在区间中间选个点那不是跟自己过不去嘛。为了让你彻底放心我再说一个更严谨的交换论证。假设有一个最优解为了覆盖排序后的第一个区间它在区间内选了某个点 xx 可能小于 R。现在我把这个点从 x 挪到 R。会不会让某些原本被覆盖的区间突然覆盖不到只有一种情况会某个区间包含 x 但不包含 R。这种区间的右端点必然小于 R因为如果它的右端点大于等于 R且它的左端点小于等于 x 小于等于 R那 R 一定在它里面。但题目里所有区间的右端点都大于等于第一个区间的右端点 R若相等也包含 R 或可能不包含如果右端点等于R左端点可能在x和R之间? 如果左端点 x则它不包含x矛盾所以唯一可能破坏覆盖的区间右端点小于R而这样的区间在当前阶段并不存在因为我们选的就是右端点最小的区间。所以把 x 替换成 R 后覆盖情况不会变差我们总能构造出一个包含 R 的最优解。把这个区间解决掉把它覆盖到的所有区间都划掉剩下的问题还是“选最少的点覆盖剩下的区间”继续如法炮制即可。这就是贪心正确性的完整证明。3.2 为什么不能按左端点排序一个反例就够了见过太多学生一上来就按左端点排序我估计是受了上一道“合并区间”例题的影响。左端点排序在“求覆盖总长度”的时候是对的但在这道题里会出大问题。看这组区间[1,5]、[2,3]、[4,6]。正确答案是 2因为 [2,3] 和 [4,6] 中间隔着空当至少两个点。如果按左端点升序排序顺序是 [1,5]、[2,3]、[4,6]。按“取第一个区间右端点”的做法第一个点取 5last 5扫描到 [2,3] 时判断2 5为假于是代码认为 [2,3] 已经被覆盖了跳过扫描到 [4,6]4 5为假也认为被覆盖了。最后输出 1。可实际上点 5 根本不在 [2,3] 里答案自然错了。问题的根源在于按左端点排序后先处理的区间右端点可能非常大导致后续小右端点区间虽然左端点小、但右端点更小根本无法被那个很靠右的点覆盖。而我们贪心判断的l last只检查了左端点它假设的是“当前区间的右端点一定比 last 大”这个假设只有在按右端点排序后才成立。按左端点排序时这个假设直接崩了判断条件也就失效了。3.3 为什么不能按区间长度排序或选“被覆盖最多”的点还有人会想区间短是不是优先覆盖它更划算我拿一个例子对比区间 [1,10]、[2,3]、[4,5]。按长度排序最短的 [2,3] 先处理取点 3覆盖前两个再处理 [4,5]左端点 4 大于 3取点 5答案 2。但正确答案也是 2似乎碰巧对。可如果换成 [1,6]、[2,3]、[4,5]、[7,8]按长度排序先处理 [2,3] 取 3覆盖 [1,6]再处理 [4,5] 取 5覆盖 [1,6]处理 [7,8] 取 8答案 3。但最优解可以取 3 和 8 两个点覆盖全部3 在 [1,6] 和 [2,3] 里8 在 [7,8] 里但 [4,5] 呢[4,5] 没有被 3 或 8 覆盖所以取3和8不够。让我重新构造。实际上按长度排序的贪心几乎都不可靠你会发现很难找到一个万能反例因为排序依据与覆盖逻辑脱节。不必多举记住“长度”不是本题的关键信息右端点才是。另外有人想过“先找被最多区间覆盖的整数点选它然后删掉被覆盖的区间重复”也就是每次选“最热门的点”。这个思路实现起来很麻烦而且正确性需要额外证明。在竞赛里一个不能快速证明的贪心就像走钢丝样例过了不代表数据能过。相反右端点排序的贪心证明干净利落写起来又短没有理由换别的方案。4. 代码实现一个用起来很顺手的C模板说了这么多该上代码了。下面的写法是我在课堂上一贯推荐的注释都写在关键位置#include bits/stdc.h using namespace std; struct Interval { int l, r; } a[1005]; bool cmp(const Interval x, const Interval y) { if (x.r ! y.r) return x.r y.r; // 按右端点升序 return x.l y.l; // 右端点相同时左端点升序不影响结果 } int main() { int n; cin n; for (int i 0; i n; i) { cin a[i].l a[i].r; } sort(a, a n, cmp); int ans 1; // 第一个点已经放在 a[0].r int last a[0].r; for (int i 1; i n; i) { if (a[i].l last) { // 注意是 不是 ans; last a[i].r; } } cout ans endl; return 0; }核心逻辑就三句排序、初始化、扫描。这个模板你背下来不难但关键是要理解a[i].l last这条判断的意思。它的语义是当前已经放好的点last不在当前区间 [l,r] 里。因为按右端点排序当前区间的右端点一定大于等于上一个处理过的区间的右端点所以只要last不小于llast就落在当前区间内。一旦发现l last说明last在区间左边够不到了必须在当前区间里补一个新点。新点放哪儿当然放右端点a[i].r因为它最靠右对未来区间最“友好”。为什么我强调初始化要单独处理第一个区间因为这样可以完全避免“当前区间是第一个区间”的特殊情况。有些写法是这样int ans 0; int last -1; for (int i 0; i n; i) { if (a[i].l last) { ans; last a[i].r; } }这种写法利用last -1保证第一个区间左端点一定大于 -1 从而必被选点代码更短。但问题在于有些题目区间的坐标可能是负数比如 [-5,3]、[-8,-2]此时左端点 -8 不大于 -1导致第一个区间不会触发选点逻辑答案错误。如果你确定坐标非负这样写没问题但为了稳妥我建议还是用第一种写法先给ans1, lasta[0].r再循环从 1 开始思路可读性也更好。走一遍样例验证。原样例区间为 [3,6]、[2,4]、[0,2]、[4,7]按右端点排序得到 [0,2]、[2,4]、[3,6]、[4,7]。初始化ans 1last 2。然后区间 [2,4]l22 2为假跳过。点 2 确实在 [2,4] 内。区间 [3,6]l33 2为真放新点ans2last6。区间 [4,7]l44 6为假跳过。点 6 在 [4,7] 内。最终输出 2。放的点是 2 和 6但如果你手算选 2 和 4也能覆盖全部区间说明这题的答案不唯一但最小数量唯一。贪心算法给出的只是其中一种可行结构。复杂度方面排序 O(n log n)扫一遍 O(n)总时间复杂度 O(n log n)空间 O(n)。对一本通这个量级的数据来说绰绰有余。如果题目要求输出具体选出的点可以在每次ans时把last存进一个vectorint最后输出即可不影响核心逻辑。5. 这三个坑我见学生踩了不止一次5.1 边界条件写成答案平白无故多 1这是最常见的一类错法。区间 [0,2] 和 [2,4]显然在点 2 放一个点就能同时覆盖两个区间。代码里如果写成if (a[i].l last) { ans; last a[i].r; }那么扫描到 [2,4] 时l2last22 2成立于是新增一个点 4答案从 1 变成 2。为什么错因为闭区间的左端点等于last时last正是当前区间左端点本身肯定在区间内不该新增点。只有一个点的坐标严格小于当前左端点时才说明它落在区间外面。所以判断必须是l last。这种差一个等号的错误在练习时几乎每个人都犯过但最好在第一次写这道题时就把它刻在脑子里。我后来让学生自查时会专门问一句“这个点如果是区间的左端点算不算在区间里”一句话就能避免这个WA。5.2 排序关键字写反或者写成了按左端点排序有些同学其实知道要排序但手一滑把cmp里的x.r y.r写成了x.l y.l。前面已经给过反例。再敲一遍[1,5]、[2,3]、[4,6]按左端点排序后贪心会输出 1正确答案是 2。排序是贪心的地基地基错了后面分析得再漂亮也没用。我建议把比较器写成下面这种稍微冗余的形式bool cmp(const Interval x, const Interval y) { if (x.r ! y.r) return x.r y.r; return x.l y.l; }先比右端点再比左端点。右端点相同的情况其实不影响结果但这样写能明确告诉读代码的人这道题的排序关键字是右端点不是左端点。5.3 把区间合并的思维硬套在这道题上“区间合并”是另一类经典问题给定若干区间把有交集的合并成一个大区间。这题是“选点覆盖”看着都跟区间有关但目标完全不同。我前面举过 [1,2]、[2,3]、[3,4] 的例子用区间合并的思想会得到一个大区间 [1,4]然后你以为只需要一个点但实际需要两个点。因为在区间合并里[1,2] 和 [2,3] 合并成 [1,3]再和 [3,4] 合并成 [1,4]合并后的“连续段”信息丢掉了“链式重叠但无法单点覆盖全部”的关键事实。我上课时做一个动作在黑板上把三个区间画成三条线段然后拿出一支粉笔代表一个点去“戳”。你会发现粉笔放到 2 上只能戳到两条线段放到 3 上也只能戳到两条没有任何位置能同时戳到三条。学生看到这个动作立刻就能分清“合并”和“覆盖”的区别。所以如果你发现自己写着写着开始维护“当前合并区间的左右端点”赶紧停下来回到“选点”的思路上。6. 从“整数区间”延伸开这类区间贪心题的通用套路1324 虽然只是一道例题但它的思想能辐射出一整片题。我建议你学完这题后顺手把下面几个经典模型一起对比着看效果会很好。问题模型排序关键字贪心操作典型题目最少点覆盖所有区间右端点升序取当前区间右端点作为新点一本通1324、POJ 3069最多不相交区间数右端点升序每次选右端点最小且与已选区间不相交的区间活动安排、HDU 2037最少区间覆盖目标线段左端点升序每次选覆盖当前起点且右端点能延得最远的区间一本通区间覆盖问题移除最少区间使剩余区间不重叠右端点升序等价于最多不相交区间数总区间数减一下LeetCode 435看出规律没有凡是“点去覆盖区间”的题几乎都优先按右端点排序因为右端点最小的区间最“脆弱”它限制了第一个点必须放在哪儿最划算。凡是“用区间去拼一条线段”的题才优先按左端点排序因为你要从左往右一点点推进每次需要找到最能往右探的区间。这个区分特别关键。很多学生学了一大堆贪心题之后反而乱了就是因为他们只记“区间排序”没记“我是谁、要覆盖谁”。我建议大家在做题前先在草稿纸上写一句话我要选的是点点去覆盖线段那么每一步照顾的应该是“右端点最小的未覆盖线段”。如果题目让你用线段去覆盖一个长线段那么每一步照顾的应该是“当前能覆盖到的最右位置”。再说一个变形也能帮你加深理解POJ 1716 的 Integer Intervals。它问的是每个区间至少包含两个不同的整数点最少需要选多少个点。思路仍然是按右端点排序但每到一个区间你要检查当前已选的最后两个点是否都在这个区间内如果都不在就需要在这个区间右端点补两个点如果只有一个在就补一个点。核心还是“右端点排序 贪心地往右端点放点”只是状态从“一个 last”变成“最后两个点”。你如果能把1324吃透这个变形其实不难想出来。最后分享一点我自己的教学体会。我会要求学生在做这道题时必须自己写一个“按左端点排序为什么会错”的反例而不是直接抄我的。因为在考场上题目不会告诉你“这是区间选点题”它可能穿一件“最少放几个信号塔”的马甲也可能穿一件“最少安排几个检查点”的马甲。你能不能在读完后两秒钟内想到按右端点排序、想到判断条件是l last靠的就是这种“把模型刻在骨子里”的熟练度。这道题是典型的“会者不难难者不会”。把样例手推一遍把三个坑记熟再动手写几行代码你会发现整数区间真的只是入门。接下来再去碰 POJ 3069、雷达覆盖、活动安排你会觉得它们背后都是同一个骨架找到一个最“急着被处理”的区间把点死死放在它的右端点上然后继续往右扫。就这么简单但就是这么需要动脑。
阅读完成 · 觉得有帮助？
