区间覆盖：每次把边界推得最远

1 问题：用最少的区间铺满一段路

给出一些区间，选出尽可能少的区间，覆盖整个目标范围；如果做不到，就报告无解。

可以把它想成铺路：每块木板只能放在指定的位置，允许木板重叠，但不能留下缺口。我们想用最少的木板，从起点一直铺到终点。

这和 雷达设备 里的「区间选点」不同：

• 区间选点：给定区间，选尽量少的点，让每个区间里都有点。
• 区间覆盖：给定区间，选尽量少的区间，让目标范围里的每个位置都被盖住。

对象都是区间，选的东西却不一样，不能只看见「区间」就照搬按右端点排序的做法。

2 例题：搞清洁

题目：luogu P2684: 搞清洁。

有 $N$ 头奶牛，第 $i$ 头只能在时间段 $l_i,l_i+1,\ldots,r_i$ 工作。一天共有 $T$ 个时间段，编号为 $1,2,\ldots,T$。

选择尽可能少的奶牛，使每个时间段都有至少一头奶牛工作。如果无法覆盖，输出 -1。

数据范围：$1\le N\le25000$，$1\le T\le10^6$。

输入格式：第一行是 $N,T$，接下来 $N$ 行，每行是一个区间的左右端点。

输出格式：最少的奶牛数，或无解时的 -1。

1
2
3
4
5
6
7
8

输入：
3 10
1 7
3 6
8 10

输出：
2

选择 $[1,7]$ 和 $[8,10]$，就覆盖了所有时间段。

3 从第一个缺口出发

假设已经连续覆盖了 $[1,cur]$。初始 cur = 0，表示还没有覆盖任何时间段。

接下来最要紧的不是「哪里能盖得多」，而是：

第一个缺口 $cur+1$，谁来覆盖？

如果跳过它，即使把右边很长的一段盖住了，整条路也仍然没有铺通。

能覆盖这个缺口的区间满足

它们都只花费一次选择，所以应该比较什么？比较右端点：能把连续覆盖边界推得越远，留给后面的任务就越少。

实现时可以只筛选 $l_i\le cur+1$，再取右端点的最大值，并令 best 初始等于 cur。那些右端点不超过 cur 的区间不会更新 best，自然就被排除了。

3.1 为什么不是选最长的区间

目标是覆盖整数点 $1\sim10$，有三个区间：

$[3,10]$ 虽然最长，却不能独自作为第一步：位置 $1$ 还没有被覆盖。

即使已经限定了「能接上」，也不能只比较区间长度。例如当前覆盖到 $5$，候选为 $[1,8]$ 和 $[5,10]$：前者更长，后者却能把边界推到 $10$，而不是 $8$。

已经覆盖的左半边不必重复计分；我们需要的是向右延伸，而不是区间本身有多长。

4 正确性：把最优解的一步换成我们的选择

直觉说「推得远不会吃亏」，证明必须回答：换成它以后，会不会丢掉原来覆盖的位置？

这里并没有声称「$g$ 包含 $o$ 的整个区间」：$g$ 的左端可能比 $o$ 更靠右。真正起作用的是：左边已经被覆盖，我们只需保证缺口以右不变差。

4.1 无法推进为什么就是无解

若所有满足 $l_i\le cur+1$ 的区间，其右端点都不超过 cur，那么它们都盖不到缺口。

剩下的区间左端点大于 $cur+1$，也盖不到缺口。因此不是「这一步选得不好」，而是没有任何区间能覆盖这个位置，任何方案都无能为力。

5 先写正确：不排序，每轮重扫

最直接的实现，每次都从头检查全部区间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

long long cur = 0;
int ans = 0;
while (cur < t) {
    long long best = cur;
    for (int i = 0; i < n; i++) {
        if (seg[i].l <= cur + 1) {
            best = max(best, seg[i].r);
        }
    }
    if (best == cur) {
        cout << -1 << '\n';
        return 0;
    }
    cur = best;
    ans++;
}
cout << ans << '\n';

这已经是正确的贪心，不要求输入有序。每次选完一个区间，它就不可能再次延伸边界，因此成功选择最多 $N$ 次。

但每轮都扫描 $N$ 个区间，最坏需要 $O(N^2)$ 时间。例如用 $[1,1],[2,2],\ldots,[N,N]$ 覆盖 $1\sim N$，就需要扫描 $N$ 轮。

接下来的排序不是为了改变贪心，而是为了更快地找到同一个贪心选择。

6 再做得快：左端点排序，指针只走一遍

6.1 旧候选为什么可以丢掉

一轮结束后，新的 cur 是本轮所有候选右端点的最大值。所以本轮看过的每一个区间都满足

它们以后都不可能把覆盖边界推得更远，因此没有必要重新检查，也不需要把它们放进堆里保留。

6.2 未来候选为什么不会漏掉

把区间按左端点升序排序，用 j 指向第一个尚未扫描的区间。

• 只要 seg[j].l <= cur + 1，就检查它的右端点，然后让 j 右移。
• 遇到左端点太大的区间就停止。排序保证后面的左端点更大，本轮也都不满足条件。
• 本轮扫描结束，才把 cur 更新为 best，并把答案加一。

6.3 样例走一遍

排序后是 $[1,7],[3,6],[8,10]$。

第二轮扫到 $[3,6]$ 时，它已经不能延伸边界，忽略即可。

6.4 完整 C++17 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 25000 + 5;

// 区间结构体：每头奶牛工作的起止时间段
struct Segment {
    ll l;
    ll r;
};

// 按左端点升序排序；若左端点相同则按右端点升序排序
bool cmp(const Segment &a, const Segment &b) {
    if (a.l != b.l) return a.l < b.l;
    return a.r < b.r;
}

ll n, t;
Segment seg[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n >> t)) return 0;

    for (ll i = 0; i < n; i++) {
        cin >> seg[i].l >> seg[i].r;
    }

    sort(seg, seg + n, cmp);

    ll cur = 0; // 当前已经连续覆盖到时间点 cur
    ll ans = 0; // 选用的最少奶牛数量
    ll j = 0;   // 扫描区间的双指针

    while (cur < t) {
        ll best = cur; // 记录能覆盖 cur + 1 的所有候选区间中，最远的右端点
        while (j < n && seg[j].l <= cur + 1) {
            if (seg[j].r > best) {
                best = seg[j].r;
            }
            j++;
        }

        // 如果没有区间能接上当前缺口，说明无法完全覆盖
        if (best == cur) {
            cout << -1 << "\n";
            return 0;
        }

        cur = best;
        ans++;
    }

    cout << ans << "\n";
    return 0;
}

6.5 复杂度

排序花费 $O(N\log N)$。虽然扫描写成两层 while，指针 j 在所有轮次中一共只增加 $N$ 次，成功轮次也不超过 $N$，所以排序后的部分总计 $O(N)$。

总时间复杂度为 $O(N\log N)$，存储区间的空间为 $O(N)$。

7 连续线段版本：为什么不能加一

若目标是非退化的实数线段 $[L,R]$，其中 $L<R$，算法思路不变，但边界约定必须改变。

连续版本初始 cur = L 表示从左端点出发准备延伸，不是说已经选过一个区间。第一轮仍要找左端点不超过 $L$、右端点大于 $L$ 的区间。

实数轴上不能跳过任何空隙，所以 $[1,7]$ 后面可以接 $[7,10]$，不能接 $[8,10]$。若题目允许 $L=R$，目标退化成单点，应另外判断是否存在区间包含这个点，而不是直接返回零。

不要把这个改动理解成「整数题加一，浮点题减一个误差」。先弄清题目要求覆盖的是哪些位置，再写衔接条件；若确实使用浮点数，还需要按题目精度要求处理比较误差。

8 边界自查

9 总结：选得对，与找得快

练习时先完成 luogu P2684: 搞清洁，再尝试不看代码，独立解释三个问题：为什么看第一个缺口？为什么选最远？为什么扫描过的区间不必再看？

10 相关题解