形式化题目

给定 $N$ 个整数闭区间 $[l_i,r_i]$，选出尽可能少的区间，使每个整数点 $1,2,\ldots,T$ 都被至少一个所选区间覆盖。不存在这样的选择时，输出 -1。

原题中，一头奶牛对应一个可选区间，选择的区间数就是安排工作的奶牛数。

这里覆盖的是整数点，不是实数轴上的所有位置。因此，$[1,7]$ 和 $[8,10]$ 可以接起来覆盖目标，中间没有遗漏的整数点。

解法路线

先确定每步该选哪个区间，再优化寻找它的过程。下文的小规模层用于解释性能递进，不对应题面未提供的子任务分数。两版实现使用同一个贪心，区别在于是否反复检查旧区间；正式主解是 main.cpp。

下表比较两层的扫描方式与适用范围，其中 $ans$ 表示成功覆盖时选出的区间数。

排序不是贪心成立的前提。它使候选区间按顺序出现，才允许指针只向前移动；解法一先保证选得对，解法二再保证找得快。

子任务解法：不排序，每轮重扫（解法一）

思路

假设已经覆盖了 $[1,cur]$，还没有解决的第一个位置就是 $cur+1$。下一步必须找一个能覆盖它的区间，否则即使覆盖了更靠右的位置，也仍然留下缺口。

一个区间能接上并扩大当前覆盖范围，当且仅当

这些候选都只需要选一次，区别是能向右延伸多远。右端点越大，留下的未覆盖后缀越短，因此尝试取右端点最大的那个。

初始令 cur = 0、ans = 0。每轮先令 best = cur，再从头检查全部 $N$ 个区间。对满足 l <= cur + 1 的区间，用其右端点更新 best。

• 若 best == cur，没有区间能覆盖第一个缺口，输出 -1。
• 否则令 cur = best，并将 ans 加一。
• 当 cur >= T 时，全部目标整数点都已覆盖，输出 ans。

best 从 cur 开始，右端点不超过 cur 的旧区间不会让它变大，不需要额外标记哪些区间已经选过。

为什么选最远的不会吃亏

比较的对象是：在已经覆盖相同前缀的前提下，补全剩余部分所需的区间数。

1. 取一个使用区间数最少的补全方案。它必有一个区间 $o$ 覆盖 $cur+1$，否则该点无人覆盖。
2. 设贪心选出的区间为 $g$。它也覆盖 $cur+1$，且 $r_g\geqslant r_o$。
3. 用 $g$ 替换 $o$。原前缀 $[1,cur]$ 已被先前的选择覆盖；在这个前缀以右，$o$ 能覆盖的整数点都在 $[cur+1,r_o]$ 内，$g$ 也能覆盖它们。因此替换后不会出现新缺口，区间数也不增加。
4. 所以至少存在一个最优补全方案包含这次贪心选择。选定它后，对新的未覆盖后缀重复同样的论证，便能逐步得到一个最优解。

注意，$g$ 不一定包含 $o$ 的整个区间；它可能起点更晚。交换仍然安全，是因为左侧已经由固定的前缀覆盖了。这也是维护“连续覆盖前缀”的用途。

若最大右端点仍不超过 cur，则所有左端不大于 $cur+1$ 的区间都到不了缺口；左端更大的区间又从缺口之后才开始。因此不是选错了区间，而是任何方案都无法覆盖该点。

上述论证只使用了候选的端点，没有要求它们按某种顺序存储。

代码

这份实现不排序，每轮的 for 都从下标零开始，直接对应“枚举所有候选”。

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
62
63
64
65/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-11-10 08:11
 * update_at: 2026-11-10 08:40
 *
 * 说明：本文件是「不排序、每步从头扫全部 N 个区间」的对照版本，
 * 用来演示同一个贪心在不排序时的写法与代价。
 * 正确性与 main.cpp 相同，但复杂度退化为 O(N * ans)。
 */
#include <iostream>
using namespace std;

typedef long long ll;

const int MAXN = 25000 + 5;

// 区间结构体：每头奶牛工作的起止时间段
struct Segment {
    ll l;
    ll 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;
    }

    // 不排序：不依赖区间顺序
    ll cur = 0; // 当前已经连续覆盖到时间点 cur
    ll ans = 0; // 选用的最少奶牛数量

    while (cur < t) {
        ll best = cur; // 记录能覆盖 cur + 1 的所有候选区间中，最远的右端点

        // 每一轮都从头扫全部 N 个区间
        for (ll i = 0; i < n; i++) {
            // 该区间能接上当前缺口 [cur + 1, ...] 才可用
            if (seg[i].l <= cur + 1 && seg[i].r > best) {
                best = seg[i].r;
            }
        }

        // 如果没有任何区间能让 cur 前移，说明出现断档，无法完整覆盖
        if (best == cur) {
            cout << -1 << "\n";
            return 0;
        }

        cur = best;
        ans++;
    }

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

复杂度与瓶颈

成功覆盖时一共选择 $ans$ 次，每次检查 $N$ 个区间，时间复杂度为 $O(N\cdot ans)$。无解时还可能多一次失败扫描；更统一的写法是 $O(N(ans+1))$，这里无解时的 $ans$ 指失败前的选择次数。

每次成功推进后，刚选的区间以及本轮所有更短候选都不能再次延伸前缀，所以成功选择不超过 $N$ 次。最坏时间为 $O(N^2)$：例如依次用 $[1,1],[2,2],\ldots,[N,N]$ 覆盖 $[1,N]$，就需要 $N$ 轮全扫。

当 $N=25000$ 时，$N^2=6.25\times10^8$，在一秒时限下有超时风险。这份写法是正确性基线，不能因样例通过就认为它适合完整规模。存储区间需要 $O(N)$ 空间。

正解

思路

解法一的浪费在于：上轮已经比较过的区间，下轮仍要再比较一次。要省掉这些检查，需要分别回答两个问题：哪些区间可以永久丢弃，哪些区间还必须留待以后？

已经纳入候选的区间可以丢弃。 一轮结束时，新的 cur 等于本轮最大的右端点。本轮扫描的每个区间都满足 $r_i\leqslant cur$，以后即使能接上，也不可能让前缀继续延长。之前各轮扫描过的区间同样如此。

当前左端太大的区间不能直接丢弃。 它们现在到不了缺口，但前缀扩大后，可能恰好成为下一步的选择。因此需要把它们留在尚未扫描的部分。

按左端点升序排序后，这两种处理能由一个指针完成：

1. j 指向第一个尚未扫描的区间，每轮令 best = cur。
2. 只要 j < n 且 seg[j].l <= cur + 1，就比较该区间的右端点，并将 j 加一。
3. 遇到左端太大的区间时停住。因为已经排序，后面的左端只会更大，本轮都不必看；它们留待后续轮次处理。
4. 与解法一相同，best == cur 时无解，否则更新 cur = best，答案加一。

这里的 best 可以每轮重新设为 cur，不必保留上一轮候选集，因为旧候选已经全部不能继续延伸。排序只改变寻找候选的方式，不改变实际的贪心选择，因此解法一的正确性证明仍然适用。

为什么不能不排序却保留指针

“cur 单调增加”不代表原数组中的候选会按顺序出现。例如目标为 $[1,5]$，输入区间按 $[3,5],[1,2]$ 的顺序存储。

• 若照搬主解的循环，cur = 0 时看见第一个区间的左端为 $3$，便停止扫描，错误地报告无解，漏掉了后面的 $[1,2]$。
• 若遇到左端太大的区间就将 j 后移跳过，又会永久丢掉 $[3,5]$。选了 $[1,2]$ 后本该回看它，指针却已经越过了它。

正确答案应选这两个区间。无序数组里，暂时不可用不等于以后不可用；排序后，指针在第一个暂不可用区间处停下，才能安全地保留全部未来候选。

因此两种组合都成立：不排序就每轮重扫，排序后才用单调指针。排序建立了候选出现的顺序，最远延伸的选择则保证已处理候选不会再有用，两者共同支持一次性扫描。

样例推演与边界

样例区间为 $[1,7]$、$[3,6]$、$[8,10]$，目标为 $[1,10]$。下表记录排序版每轮新扫描的区间与覆盖前缀。

第二轮虽然也扫到 $[3,6]$，但它的右端不超过当前前缀，不会改善 best。最终选择 $[1,7]$ 和 $[8,10]$，答案为 2，与给定样例输出一致。

检查边界时，应围绕第一个缺口判断：

• 若只有 $[1,3]$ 和 $[5,7]$，目标右端为 $7$，则位置 $4$ 无法覆盖，答案为 -1。
• 当 $T=1$ 时，有区间覆盖整数点 $1$ 就输出 1，否则输出 -1。
• 若一个区间已经覆盖整个目标，成功推进一次便结束；判断条件是 cur >= T，不要求恰好等于 $T$。
• 左端相同时，仍须比较这些区间的全部右端点。代码额外按右端点升序打破平局，但不依赖这一平局顺序。

代码

j 只在内层循环中增加，外层循环不会把它归零。cur、best 和端点在实际代码中使用 ll，避免把过程记录中的示意类型与源码混淆。

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
62
63
64
65
66
67
68/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-11-10 08:11
 * update_at: 2026-11-10 08:34
 */
#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;
}

复杂度

排序需要 $O(N\log N)$ 时间。内层循环看似位于外层循环中，但 j 从零增加到至多 $N$，全部轮次合计只扫描 $N$ 个区间；成功轮次也不超过 $N$，因此排序后的部分总共为 $O(N)$。

总时间复杂度为 $O(N\log N)$，存储区间所需空间为 $O(N)$。与解法一相比，增加一次排序，换掉了每一轮的全量扫描。

总结

本题有两个不同的正确性问题：选哪个区间，以及什么时候可以不再看某个区间。

前者靠最远延伸的贪心：在能接上第一个缺口的区间中，选右端最远的一个，交换后不会增加区间数。后者靠排序与已处理区间的淘汰性质：未来候选留在指针之后，旧候选不再具有延伸能力。

因此，“贪心不依赖输入顺序”与“单调指针依赖排序”并不矛盾。先用全扫把选择写正确，再用有序性消除重复检查，就把 $O(N\cdot ans)$ 优化到了 $O(N\log N)$。