当前位置：首页 > news >正文

区间选择类问题笔记

news 2026/5/3 21:55:43

区间选择类问题笔记

下文不考虑无解的情况。

如果数组爆了需要离散化，或者使用 umap。

1 P1803/P2970/P6244

从 \(n\) 个区间里选择一些区间，使得选的区间两两不交，同时最大化选的数量。

做法：

按右端点排序，每次贪心地从前往后选满足条件的区间。

2 P1668/P2684

从 \(n\) 个区间里选择一些区间，在这些区间能覆盖 \([1,t]\) 内所有整数点的前提下，使得选择的区间个数最小。

做法：

假设我们要选一个区间作为来覆盖起点，为了让使用的区间最少，我们的下一个区间应该选谁？

显然，必须与当前区间相交（或首尾相接），且在所有能接上的区间里，我们应该选择右端点延伸得最远的那个。

我们便一直重复这个过程，直到选出的区间覆盖 \([1,t]\)。

实现 1：

按左端点排序，枚举 1~t 中的整点，如果当前点没有被覆盖，则选择能够覆盖该点的，右端点最远的区间。可用二分/双指针找到该区间。

时间复杂度 \(O(n \log n+t)\)。

实现 2:

按左端点排序，维护当前已覆盖到的最右位置 pos（初始为 1）。每次在所有左端点 \(\le\) pos 的区间中，贪心选择右端点最远的那个，将 pos 更新为该右端点，直到覆盖终点。

时间复杂度 \(O(n \log n)\)。

3 SP661

给定 \(n\) 个区间 \([l, r]\)。你需要从数轴上中选择最少的点，使得每个区间都至少包含一个被选中的点。

做法：

按右端点排序。枚举区间，如果当前区间没有被选择，则选择当前区间的右端点，即最靠右的在当前区间内的点。

对于快速判断当前区间有无点被选择，我们可以仿照 Prob. #2 的做法 2，维护上一个被选的点（即当前被选到的最右位置） pos，如果 pos<l，则当前区间没有被选的点。

3p P2207

给定 \(n\) 个数对 \((a,b)\)。你需要把数轴划分成数量尽可能少的连续段，使得 \(a\) 和 \(b\) 不在同一个连续段内。

做法：

乍一看这个问题和我们区间选择的主题毫无关系。使用 Trick，把视角转化到连续段的分界点处。

要让 \(a<b\) 不在同一个段内，等价于必须在区间 \([a,b]\) 中切一刀。或者说，区间 \([a,b-1]\) 之中必须包含一个分界点。我们要最小化连续段数量，便是最小化分界点数量。

令 \(l=a, r=b-1\)，问题便转化成了 Prob. #3。答案即为 Prob. #3 的结果加一。

3.5 P11232 核心

给定 \(n\) 个区间 \([l, r]\) 和 \(m\) 个点 \(p\)。你需要从 \(m\) 个点中选择最少的点，使得每个区间都至少包含一个被选中的点。

Prob. #3 是 \(p\) 是整条数轴的情况。

做法 1：

按右端点排序，将点排序。枚举区间，如果当前区间没有点被选择，用二分/双指针找到最靠右的在当前区间内的点，选择该点。

做法 2：

将这 \(n\) 个区间的左右端点离散化至这 \(m\) 个点。具体地，将点排序，对于每一个区间 \([l,r]\)，二分出在当前区间内的点的范围 \([l',r']\)，然后就针对转化后的新区间做一边 Prob. #3。这个方法对大部分有限制点集的问题都有用。

4 P1250/P10934/P1645/P1986

给定 \(n\) 个区间 \([l, r]\)。每个区间有一个属性 \(t\)。需要从数轴上选择最少的点，使得 \(n\) 个区间中的每一个区间 \(i\) 都至少包含 \(t_i\) 个被选中的点。

Prob. #3 是 \(t=1\) 的特例。

做法：

按右端点排序，将点排序。存一个 bool 数组表示每个点是否被选。枚举区间，如果当前区间内选的点个数 need 大于等于 \(t\)，则可以跳过。否则贪心地从这个区间右往左选 need 个未选点。

4 Ex SP116/UVA1723/(P11453 改)/(AT_abc216_g 改)

Prob. #3 + \(n,m \le 10^5\)。

Prob. #3.5 是 P11453 和 AT_abc216_g 的 \(t=1\) 且数据范围小的弱化版。P11453 和 AT_abc216_g 仍然可以按照 Prob. #3.5 的方法转化成当前问题。

做法 1：

Prob. #3 做法的时间复杂度是 \(O(n \log n + m \log m + nm)\)，难以通过。

注意到瓶颈在于解决该问题：

遍历 \([l,r]\) 来统计区间内已选了多少点。
遍历 \([l,r]\) 来找到最右的 \(k\) 个未选点

用线段树维护 \([l,r]\) 内已选点的个数和索引值最大的未被选择的点，区间查询和/最大值与单点修改。

仔细分析下时间复杂度就是 \(O(n \log n + (n+m) \log m)\) 了。

做法 2：

维护索引值最大的未被选择的点的个数可以不用线段树维护，也可用并查集。具体地讲，令 fa[j] 表示小于等于 \(j\) 的最靠右的尚未被选择的点。一旦 \(j\) 被选择，小于等于 \(j\) 的最靠右未选择点，自然就变成了小于等于 \(j-1\) 的。所以当你选择 \(j\) 时，我们令 fa[j] = find(j-1)。修改之后的查询，便可使用路径压缩来更新 fa[j]。这样这样能将线段树的 \(\log\) 变成反阿克曼函数 \(\alpha(n)\)。当然已选点个数的维护还是要带个 \(\log\) 的。

做法 3：

差分约束。

设 s[k] 表示 0~k 中选择的点的个数（假设 \(l \ge 0\)）。此时 s[k]-s[k-1] 就表示第 \(k\) 个点有没有被选，显然 s[k]-s[k-1]>=0，s[k]-s[k-1]<=1。为了满足原题 t 的约束，对于每个区间 [l,r]，s[r]-s[l-1]>=t_i。

我们的目标是最小化 s[max(r)]。跑一遍 SPFA 最长路就可以找到满足限制的最小的。

做法 4：

很不幸的是，AT_abc216_g 会卡 SPFA。

我们为何不转化为最短路模型，也就是最大化一个东西呢？

设 c[k] 表示 0~k 中不选择的点的个数。c[k]-c[k-1]>=0，c[k]-c[k-1]<=1，c[r]-c[l-1]<=r-l+1-t_i。

最大化 c[max(r)]。注意到边权都为正的，就可以放心地跑 Dijkstra 了。

延伸：为什么最大化 c 要跑最短路？

因为最短路算法跑完后，对于一个固定的点 \(v\)，有很多入边 \((u_1,v,w_1)\)，\((u_2,v,w_2)\)……，它们都会满足 dis[u]+w>=dis[v]（也就是 dis[v]-dis[u]<=w）。最短路算法会恰好选择 dis[v]=min(dis[u]+w)，而不是这个数减去 \(1\)，或减去 \(2\)，即使它们也合法。此时，c[max(r)] 这个数便是在 dis[0]=0 固定的情况下，满足这些约束条件的最大值。

5 CF1249D1/CF1249D2/(P3602 改)

从 \(n\) 个区间里选择一些区间，使数轴上每个点都被不超过 \(m\) 个区间覆盖。最大化选取的区间数。

做法：

按右端点排序，在数轴上维护线段树，每次贪心地从前往后枚举区间，如果该数轴上该区间内的最大值小于等于 \(m\) 则选，然后区间加一。

6 P7391 改

你最多有 \(m\) 个轨道（或 \(m\) 台机器），有 \(n\) 个区间，每个区间表示一个任务，需要占用一个轨道从时间 \(l_i\) 到时间 \(r_i\)。在同一轨道上的任务不能重叠。你的目标是选择最多的任务，使得它们可以被这 \(m\) 个轨道处理。

形式化地：从 \(n\) 个区间里选择一些区间，使得它们可以被划分为 \(m\) 个子集 \(S_1, S_2, \dots, S_m\)，其中每个 \(S_j\) 内部的区间两两不相交。最大化选取的区间数。

P7391 是最小化未被选取的区间数。

Prob. #1 是 \(m=1\) 的特例。

P2255 是 \(m=2\) 的特例。

做法：

按右端点排序。枚举任务，用小根堆维护每条轨道此时最后一个任务的结束时间，这样便可找到结束时间最早的此时已经空闲了的轨道。如果存在，便将当前任务派发给该轨道处理，并更新当前轨道结束时间；否则，我们就新开一条轨道处理这个任务，如果开完之后轨道条数 \(> m\) 了，那就只能不选择这个任务处理了。答案便是 \(n\) 减去决定不处理的任务数量。

Bonus : Prob. #5 和 Prob. #6 等价，即对于同样的输入，答案是一样的。我们将会在后文对它们的等价性进行深入的证明。

6.5 P7913 改

你总共有 \(m\) 个轨道，有 \(n\) 个区间，每个区间表示一个任务，需要占用一条轨道从时间 \(l_i\) 到时间 \(r_i\)。在同一轨道上的任务不能重叠。

与 Prob. #6 不同的是，本题有先到先得的特殊限制：任务的处理必须严格按时间轴（即左端点）先后顺序进行。如果任务到达时有空闲轨道，则该任务必须占用一条轨道直到 \(r_i\)；如果没有空闲轨道，该任务直接被丢弃。你无法为了容纳后续可能出现的大量短任务，而主动拒绝当前到达的长任务。

本题是 P7913 的 \(m_B=0\) 的特例。

做法：

Prob. #6 不要求先到先得，我们便可以顾全大局地贪心选；可本题我们必须遵循时间流逝的规律，所以我们按左端点排序。

不过仍然可以复用 Prob. #6 贪心的思路。枚举区间，一样地，用小根堆维护每条轨道此时最后一个任务的结束时间。先将所有已经完成的任务进行清理，再尝试安排当前任务：如果小根堆元素数量小于 \(m\)，说明还有空闲的轨道，根据限制，我们不得不强制将其派发给这个轨道。否则，当前任务只能被丢弃。

7 P2859 改

你需要设置多个轨道。共有 \(n\) 个区间，每个区间代表一个任务，该任务占用一个轨道，时间范围从 \(l_i\) 到 \(r_i\)。同一轨道上的任务不能重叠。你的目标是确定处理所有任务所需的最少轨道数量。

形式化地：将 n 个区间划分为多个子集 \(S_1, S_2, \dots\)，其中每个 \(S_j\) 内部的区间两两不相交。最小化划分出的子集数量。

和 Prob. #6 很像，可目标不同。

做法 1：

按左端点排序。枚举任务，用小根堆维护每条轨道此时最后一个任务的结束时间，这样便可找到结束时间最早的此时已经空闲了的轨道。如果存在，便将当前任务派发给该轨道处理，并更新当前轨道结束时间；否则，我们就新开一条轨道处理这个任务。

做法 2：

显然，最少的轨道数量等于整个时间段中需要同时使用的轨道数量的峰值。

我们遍历每一时刻，统计在这一时刻有多少任务正在执行，此时这些任务的每个都不得不占用一条轨道，答案便是它们的 max。

为了统计，我们可以使用扫描线/差分的思想，维护一个值域桶，在预处理时，对于每一个区间 \([l,r]\)，令桶 add(l,1)，add(r+1,-1)。对于时刻 t，正在执行的任务数量便是 sum(1,t)，这个求和边枚举 t 边算即可。

思考题 1：Prob. #7 的做法 1 和 Prob. #6 的解法有哪些区别？为什么？

思考题 2：P2859 需要输出方案，即输出每个任务被派发给了哪条轨道处理。做法 1 很容易，对于做法 2，如何实现这一点？

8 P14049/CF45D

给定 \(n\) 个区间 \([l, r]\)。你需要选出尽可能多的区间，从而可以通过为数轴上每个整点分配最多一个归属区间，使得每个区间都至少包含一个归属于其的点。

与 Prob. #4 和 Prob. #6 有点像，主要变动在于，每个点最多只能分配给一个区间，而不是能同时被多个区间覆盖。

做法 1：（类似 Prob. #6）

按左端点排序。枚举整点，用小根堆维护右端点最靠左的还没有归属点的区间。每次，先将所有右端点已经在当前点前面的区间弹出，他们已经无法被归属了。然后，将所有以当前整点为左端点的区间加入到堆内，接着将当前整点分配给堆顶，弹出堆顶。\(O(n \log n)\)。

做法 2：（类似 Prob. #4 做法 2）

按右端点排序。枚举区间，我们贪心地希望给它分配一个尽可能靠左的，大于等于 \(l_i\) 且还没被确定归属的点。这个还是可以用并查集来维护。令 fa[x] 表示大于等于 \(x\) 的这样的点。像 Prob. #4 做法 2 一样维护这个并查集即可。除了排序外是 \(O(n\alpha(n))\)。

9 CF1175E

给定 \(n\) 个区间，\(q\) 次询问，每次给出 \([x,y]\)，你需要从 \(n\) 个区间里选择一些区间，在这些区间能覆盖 \([x,y]\) 内所有整数点的前提下，使得选择的区间个数最小。

Prob. #2 是 \(q=1\)，\(x=1\)。

做法：

如果对于每一个起点都跑一遍 Prob. #2 的贪心，是 \(O(nq)\) 的。

考虑优化这个贪心的过程以减少重复。

将每一次选择新区间的过程看作从上一个区间的基础上跳一步（因为下一个区间只和上一个区间有联系），则贪心的算法本质上就是一直跳，直到覆盖给定的区间。优化这个跳的过程，条件反射地想到倍增。

按左端点排序，预处理倍增数组（f[i][k] 表示从区间 \(i\) 开始贪心跳 \(2^k\) 步到达的最远区间），先为 \(x\) 选一个能够覆盖该点的，右端点最远的区间作为初始区间，利用倍增数组快速跳转直到覆盖长度 \(\ge x-y+1\)，取最小跳转次数。

10 P10762/P6902/UVA1707

给定一个长度为 \(t\) 的环，有 \(n\) 个区域被覆盖，求最小的满足环被完全覆盖的区域数量。

就是将 Prob. #2 搬到了环上。

做法：

断环为链，就变成了一个长度为 \(2t\) 的数轴，用这 \(n\) 个区域覆盖数轴上一段长度为 \(t\) 的区间内整数点，最小化使用的区域数。

枚举这个长度为 \(t\) 的区间的起点 \(x\)，就可以看成需要覆盖 \([x,x+t-1]\) 这段区间了。

仍按照 Prob. #9 的优化方法优化即可。

11 QOJ11738

给定一棵 \(n\) 个点的树，再给定树上的 \(k\) 条链 \([u,v]\)，你需要从 \(n\) 个点中选择最少的点，使得每条链上都至少包含一个被选中的点。

做法 1：

和 Prob. #3 类似。

按每条链两端点的 LCA 的深度从深到浅排序，枚举链，如果当前链没有被覆盖，便选择该链两端点的 LCA。

对于快速判断当前区间有无点被选择，由于树上的区间关系比较复杂，我们不能使用像 Prob. #3 的方式判断。可像 Prob. #4 Ex 一样，用线段树+树链剖分维护一条链上已选点的个数，如果其大于零，则有点被选。

做法 2：

上面的具体实现太复杂了。

还是仿照 Prob. #3，可是我们不用链去找 LCA，而是对树进行后序遍历 DFS，处理完儿子后，检查当前节点能否作为某条没有被选的链的 LCA，如果可以就选上。

具体地，我们对每个点计算一个 set，记录当前子树内尚未被覆盖的，且至少有一个端点在子树内的路径编号。我们可以懒惰地利用计算完的儿子的信息。遍历完所有儿子后，如果某条链的编号同时出现在了不同儿子的集合内，说明这条链的两个端点出现在了当前节点的不同子树中，说明当前节点就是这条链的 LCA。选取当前点即可。这样，所有经过当前点的链都会被覆盖，直接清空 set，然后回溯即可。

如果当前点还是没有被选，对当前点和所有儿子的集合求并，然后往上传。启发式合并即可做到 \(O(k \log^2 k)\)。使用严格一点的启发式合并或者线段树合并可以做到单 \(\log\)。

11 Ex CF1929E/AT_abc152_f

给定一棵 \(n\) 个点的树，再给定树上的 \(k\) 条链，你需要从 \(n-1\) 条边中选择最少的边，使得每条链上都至少包含一条被选中的边。

和 QOJ11738 的区别在于将选择点换成了边。

事实上，本题虽然只和上题有这一个区别，但本题可以被证明是 NP-Hard 的，证明留作练习。

思考题：为什么本题无法使用贪心算法？

可以感性地理解为欧拉路和哈密顿路的区别。

12a Ex P3033 改

Prob. #1 的二维版本。

从 \(n\) 条线段选择一些线段，使得选的线段两两不交，同时最大化选的数量。

在探讨这个问题之前，我们先来进行一些有趣的洞察。

如果你尝试图论建模，比如：将每条线段看作一个顶点，如果他们相交，就连一条边。这类图有一个学名，就叫区间图。你会惊奇的发现，本题便可转化为求图的最大独立集问题。

NP-Hard.

可为什么一维的问题可以在 P 时间内解决？

我们来寻找一维问题的区间图的一些性质。

在一维直线上，要想让区间 A 交 B，B 交 C，C 交 D，且 D 交 A，同时 A 不交 C，B 不交 D。是不可能的。所以，一维区间图，不会出现一个长度大于等于四的空心的圈。比如 A-B-C-D-A 连成一个环，中间一定会有十字交叉的抄近道的边（即要么 \(A\) 连 \(C\)，要么 \(B\) 连 \(D\)）。我们称这类边叫做弦，定义为连接环中不相邻两点的边。

由上，一维区间图的性质便符合弦图的判定。

在图论中，没有长度 \(\ge 4\) 的无弦环的图被称为弦图。参考 OI-Wiki，它的最大独立集可以简单地 P 时间内解决。

12a P3033

可二维版本的区间图好像没有这个性质欸。

我们便可以给二维版本的题目加一点限制，使其建出来的图具有优美的性质。

好像二分图求最大独立集也非常快。不难发现，这对应着，线段之间互相平行或垂直，同时水平线段只和垂直线段相交，不会同向重叠。那么图中的每一条相交的边，必定连接着一条水平线段和一条垂直线段。

加上这个限制之后，我们便可以直接对建出的图跑网络流即可。

12b Ex P6763 改

Prob. #7 的二维版本。

将 \(n\) 条二维线段划分为多个子集 \(S_1, S_2, \dots\)，其中每个 \(S_j\) 内部的二维线段两两不相交。最小化划分出的子集数量。

还是建立区间图，将每条线段看作一个点，如果他们相交，就连一条边。本题便可转化为求图的色数问题（用最少的颜色给点染色使得所有边连接的两点颜色不同）。

NP-Hard.

同理，对于一维，求弦图的色数也是可以在 P 时间内解决的。

说到色数，我们提一嘴弦图的一个与其相关的性质：它是一张完美图。

完美图的定义&性质：图的色数 \(\chi(G)\) 严格等于最大团的大小 \(\omega(G)\)。

什么是团？团就是图的顶点的一个子集合，满足对于团内的每一对点，它们之间都在图里有一条边。最大团便是图中大小最大的团。

对应回区间图，最大团的意思就是找出最多数量的线段，它们两两互相交叉。

借二维化引出了那么多概念，我们总算可以回看到 Prob. #5 和 Prob. #6 中了。我们前面提到过，它们是等价的。

那为什么呢？我们也来对其进行图论建模：

Prob. #5：寻找一个最大子集 \(S\)，使得 \(S\) 的最大团的大小 \(\omega(S) \le m\)。因为在区间图中，显然最大团的大小就等于数轴上某一点被覆盖次数的峰值。
Prob. #6：寻找一个最大子集 \(S\)，使得 \(S\) 的色数 \(\chi(S) \le m\)。因为每一种颜色代表一个互不相交的集合（即一条轨道）。

根据完美图的性质，他们是等价的。

12b P6763

回到 12b 的正题。我们需要加一些限制。更改如下：

将 \(n\) 条二维线段划分为多个子集 \(S_1, S_2, \dots\)，其中每个 \(S_j\) 内部的二维线段两两不相交。最小化划分出的子集数量。保证每条线段的端点分别在两条不同的直线上，且这两条直线互相平行。也就是说，第 \(i\) 条线段形如 \((x_{i1},A)-(x_{i2},B) \ (A \ne B)\)。

做法 1：

尝试观察，发现：此时，两条线段不相交的判断很简单，只要形成一个 / \ 或 \ / 而非 X，V 即可。那么，两条线段 \(i,j\) 不相交便等价于 \(x_{i1}<x_{j1}\) 且 \(x_{i2}<x_{j2}\)。将每条线段按照 \(x_1\) 排序，那么划分子集时，判断两条线段能否在一个集合内，只用考虑 \(x_2\) 的数量关系。

也就是说，我们需要把所有排序后线段划分成子集，每个子集内部满足 \(x_2\) 递增，求最小子集个数。这可以用 Dilworth 定理转化为此时的按 \(x_1\) 排序后的 \(x_2\) 组成的序列的最长下降子序列长度。\(O(n \log n)\)。

做法 2：

现在建出来的二维版本的区间图有没有具有了什么优美的性质了呢？

当线段端点被限制在两条平行线上时，每一条线段本质上定义了一个逆序关系。设顶端点顺序为 \(1 \dots n\)，底端点形成的排列为 \(\pi\)。