区间问题学习笔记

之前在区间贪心专题的教学过程中，一直有一个疑惑为什么区间调度（最大不相交区间）和区间选点的代码基本一致。

现在在AI的帮助下，对这个问题有了更好的认识，也顺带从这里入手整理了区间贪心专题，分享出来希望有所帮助。

一、 三大核心区间贪心模型

假设每个区间用  表示。

1. 区间调度与区间选点（“互斥与独立”问题）

• 问题描述：
• 区间调度（最多不相交区间）：给定多个区间，选出尽可能多的区间，使得它们互不相交。
• 区间选点：给定多个区间，在数轴上选择尽量少的点，使得每个区间内至少包含一个点。
• 贪心策略：按右端点  从小到大排序。
• 核心逻辑：每次选择结束时间最早的区间（或在其右端点放一个点）。为什么？因为结束得越早，留给后面区间的空间就越大。这是一种“给未来留足余地”的策略。

2. 区间分组（“并发与冲突”问题）

• 问题描述：将所有区间分成若干组，使得每一组内的区间互不相交，求最少需要划分多少组。（例如：最少需要多少间会议室才能安排下所有会议）。
• 贪心策略：按左端点  从小到大排序。
• 核心逻辑：按时间顺序处理每一个区间。对于当前区间，如果能放进现有的某个组（即该组最晚的结束时间 ），就放进去并更新该组的结束时间；如果所有现有组都冲突，就必须开辟一个新组。通常结合优先队列（小根堆）来维护各组的结束时间。

3. 区间覆盖（“拼接与延伸”问题）

• 问题描述：给定一个目标大区间  和若干小区间，求最少需要多少个小区间才能完全覆盖这个大区间。
• 贪心策略：按左端点  从小到大排序。
• 核心逻辑：在所有能够覆盖当前起点  的区间中，选择右端点  最大（延伸得最远）的一个。选中后，将起点  更新为这个区间的右端点，继续寻找。这是一种“每次都贪图走得最远”的策略。

二、 它们的联系与本质规律

它们的联系可以通过以下三个维度来理解：

1. 排序基准的二元对立（左端点 vs 右端点）

这是区间贪心最容易让人混淆的地方，但其实规律很明确：

• 按右端点排序（聚焦于“结束”）： 适用于限制型问题（如最多不相交区间）。你关心的是这个区间什么时候结束，因为它占用的空间越少、结束越早，越不会影响后面的决策。
• 按左端点排序（聚焦于“开始”）： 适用于推进型或分配型问题（如区间覆盖、区间分组）。你必须按照时间线从左到右推进，关心的是“在当前时间点，我能用哪个区间达到最佳效果”。

2. 问题的等价性与对偶性

• 2.1 区间调度 = 区间选点：这两个问题看似不同，但代码实现几乎一模一样。你为了让选出的区间最多，其实就是在寻找尽量多的互斥的“独立事件”；而为了用最少的点穿透所有区间，你也必须把点放在互斥区间的交界处。

通俗来说，“找最多的互斥事件”和“用最少的钉子钉住所有事件”，其实是一枚硬币的正反面。

视角的切换：从“选线段”到“钉钉子”

假设面前有 5 个区间。统一按照右端点（结束时间）从小到大排序。

在“区间调度”里（求最多不相交区间）：目标是尽量多地参加活动。选中了第一个结束的活动 A。因为要参加 A，所以任何和 A 时间冲突的活动都参加不了。只能等 A 结束后，再去选下一个最早结束的活动 B。最后选出了互相完全错开的 3 个活动（比如 A、B、C）。

在“区间选点”里（求最少点穿透所有区间）：目标是用最少的钉子把所有飞镖靶（区间）钉在墙上。看着第一个飞镖靶 A，为了让这颗钉子顺便能钉住后面尽可能多的靶子，会把钉子钉在靶子 A 的最右边缘（右端点）。钉下去之后，所有包含了这颗钉子的靶子都被搞定了。接着，找到第一个没被钉住的靶子 B，再次把钉子钉在 B 的最右边缘。最后用了 3 颗钉子。

为什么它们是等价的？

仔细观察上面的过程，会发现一个现象：在“选点”时钉下钉子的位置，刚好就是你在“调度”时选出的那些区间的右端点。

它们的内在联系可以用两句话概括：

第一句：因为有  个区间互相“水火不容”，所以你至少需要  颗钉子。在区间调度中，找到了 3 个完全不相交的区间 A、B、C。既然三个在数轴上没有任何重叠的部分，那么哪怕是神仙，也绝对不可能用 1 颗或者 2 颗钉子同时穿透它们。至少需要 3 颗钉子。这就决定了选点数量的下界。

第二句：贪心策略保证了，选出的这  颗钉子，不仅能钉住这  个互斥区间，还能顺便钉住所有其他的区间。因为是按右端点排序的，每当把钉子放在某个互斥区间的右端点时，那些因为“重叠”而被在区间调度中抛弃的区间，必然会跨越这个右端点，从而被这颗钉子“免费”穿透。

这种将“最大化互斥量”转化为“最小化覆盖量”的思想，在图论中也会出现，比如二分图的最大匹配等于最小点覆盖。

• 2.2 最大不相交区间数 vs 最大重叠厚度：区间分组的最少组数，在数学上严格等于所有区间在数轴上的最大重叠层数（最大并发数）。这就把一个动态分配问题转化为了一个静态的统计问题。

3. 贪心特性的统一：极端化选择

所有的区间贪心都在做一件事：在满足当前合法性的前提下，做出最“极端”的选择。

• 选点问题：把点放在合法的最右侧（右端点），以期望顺便穿透更多后续区间。
• 覆盖问题：选择合法前提下延伸得最远的区间，以期望用最少的数量跨越目标。
• 分组问题：利用小根堆找结束时间最早的组，以最大化空间利用率。

三、 总结：

面对一道区间贪心题，可以按照这个思维框架来拆解：

1. 目标是什么？ 是求数量最大化（不相交区间）、资源最小化（分组）、还是范围最大化（覆盖）？
2. 按什么排序？ 试着推演一下：如果按左端点排序，我能顺理成章地往后推吗？如果不行，就按右端点排序。
3. 维护什么状态？ 是维护上一个选定区间的右端点（单变量），还是维护所有分组的右端点集合（堆）？

四、 可以做的练习：

CSP-S 2024 T2《超速检测 (Detect)》 CSP-S 2021 T1《廊桥分配 (Airport)》 NOI 2017《蔬菜 (Vegetables)》 NOIP 2018 提高组 T1《铺设道路 (Road)》