企业官网建设流程全解析

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 标准做法只需要五步

这道题的正解非常简洁，我建议所有学生都按下面这套流程走：

1. 读入 n 个区间，用结构体存每个区间的左端点 l 和右端点 r。
2. 把区间按右端点从小到大排序。
3. 先取排序后第一个区间的右端点，当作放置的第一个点，记录到last，答案ans初始化为 1。
4. 从第二个区间开始往后扫：如果当前区间的左端点l大于last，说明之前放的点覆盖不到它，于是在当前区间的右端点处放一个新点，ans++，更新last为当前区间的右端点。
5. 如果当前区间的左端点l小于等于last，说明last这个点已经落在了当前区间里，直接跳过，不用放新点。

为什么第一步要取排序后第一个区间的右端点？因为按右端点从小到大排序后，第一个区间是所有区间里“最急着结束”的，它的右端点最小。为了保证这个区间一定被覆盖，必须在它内部放一个点。那这个点放在哪里最好？放在它的右端点 R 上，因为其他所有区间的右端点都大于等于 R——这是排序保证的——只要某个区间的左端点小于等于 R，R 就落在那个区间里。换句话说，R 是当前情况下“最能顺带覆盖其他区间”的位置。放着这么个位置不用，反而在区间中间选个点，那不是跟自己过不去嘛。

为了让你彻底放心，我再说一个更严谨的交换论证。假设有一个最优解，为了覆盖排序后的第一个区间，它在区间内选了某个点 x，x 可能小于 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]。按“取第一个区间右端点”的做法，第一个点取 5，last = 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不小于l，last就落在当前区间内。一旦发现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，导致第一个区间不会触发选点逻辑，答案错误。如果你确定坐标非负，这样写没问题；但为了稳妥，我建议还是用第一种写法，先给ans=1, last=a[0].r，再循环从 1 开始，思路可读性也更好。

走一遍样例验证。原样例区间为 [3,6]、[2,4]、[0,2]、[4,7]，按右端点排序得到 [0,2]、[2,4]、[3,6]、[4,7]。初始化ans = 1，last = 2。然后：

• 区间 [2,4]：l=2，2 > 2为假，跳过。点 2 确实在 [2,4] 内。
• 区间 [3,6]：l=3，3 > 2为真，放新点，ans=2，last=6。
• 区间 [4,7]：l=4，4 > 6为假，跳过。点 6 在 [4,7] 内。

最终输出 2。放的点是 2 和 6，但如果你手算选 2 和 4，也能覆盖全部区间，说明这题的答案不唯一，但最小数量唯一。贪心算法给出的只是其中一种可行结构。

复杂度方面，排序 O(n log n)，扫一遍 O(n)，总时间复杂度 O(n log n)，空间 O(n)。对一本通这个量级的数据来说绰绰有余。如果题目要求输出具体选出的点，可以在每次ans++时把last存进一个vector<int>，最后输出即可，不影响核心逻辑。

5. 这三个坑，我见学生踩了不止一次

5.1 边界条件写成>=，答案平白无故多 1

这是最常见的一类错法。区间 [0,2] 和 [2,4]，显然在点 2 放一个点就能同时覆盖两个区间。代码里如果写成：

if (a[i].l >= last) { ++ans; last = a[i].r; }

那么扫描到 [2,4] 时，l=2，last=2，2 >= 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 虽然只是一道例题，但它的思想能辐射出一整片题。我建议你学完这题后，顺手把下面几个经典模型一起对比着看，效果会很好。

看出规律没有？凡是“点去覆盖区间”的题，几乎都优先按右端点排序，因为右端点最小的区间最“脆弱”，它限制了第一个点必须放在哪儿最划算。凡是“用区间去拼一条线段”的题，才优先按左端点排序，因为你要从左往右一点点推进，每次需要找到最能往右探的区间。

这个区分特别关键。很多学生学了一大堆贪心题之后反而乱了，就是因为他们只记“区间排序”，没记“我是谁、要覆盖谁”。我建议大家在做题前先在草稿纸上写一句话：我要选的是点，点去覆盖线段，那么每一步照顾的应该是“右端点最小的未覆盖线段”。如果题目让你用线段去覆盖一个长线段，那么每一步照顾的应该是“当前能覆盖到的最右位置”。

再说一个变形，也能帮你加深理解：POJ 1716 的 Integer Intervals。它问的是每个区间至少包含两个不同的整数点，最少需要选多少个点。思路仍然是按右端点排序，但每到一个区间，你要检查当前已选的最后两个点是否都在这个区间内，如果都不在，就需要在这个区间右端点补两个点；如果只有一个在，就补一个点。核心还是“右端点排序 + 贪心地往右端点放点”，只是状态从“一个 last”变成“最后两个点”。你如果能把1324吃透，这个变形其实不难想出来。

最后分享一点我自己的教学体会。我会要求学生在做这道题时，必须自己写一个“按左端点排序为什么会错”的反例，而不是直接抄我的。因为在考场上，题目不会告诉你“这是区间选点题”，它可能穿一件“最少放几个信号塔”的马甲，也可能穿一件“最少安排几个检查点”的马甲。你能不能在读完后两秒钟内想到按右端点排序、想到判断条件是l > last，靠的就是这种“把模型刻在骨子里”的熟练度。

这道题是典型的“会者不难，难者不会”。把样例手推一遍，把三个坑记熟，再动手写几行代码，你会发现整数区间真的只是入门。接下来再去碰 POJ 3069、雷达覆盖、活动安排，你会觉得它们背后都是同一个骨架：找到一个最“急着被处理”的区间，把点死死放在它的右端点上，然后继续往右扫。就这么简单，但就是这么需要动脑。