「Cleaning Shifts」清理班次

形式化题目

给定 $N$ 个闭区间 $[l_i, r_i]$ 与整数 $T$ ，求最小的子集 $S$ ，使得

\bigcup_{i \in S} [l_i, r_i] \supseteq [1, T];

若不存在这样的子集，则报告无解。区间之间允许重叠，每头奶牛要么整段使用、要么不用。

正解

思路

朴素做法与瓶颈

把"班次"看成数轴上的点，每头奶牛就是一个闭区间 $[l_i, r_i]$ ，问题即最小区间覆盖。

设 $dp[x]$ 表示铺满班次 $1 \dots x$ 所需的最少奶牛数， $dp[0] = 0$ ，其余初值为 $+\infty$ 。若一个方案的最后一头牛是 $[l, r]$ 且它盖住班次 $x$ ，那么班次 $1 \dots l-1$ 必须已经被铺满，于是

dp[x] = \min_{i:\, l_i \leqslant x \leqslant r_i} \bigl(dp[l_i - 1] + 1\bigr).

直接按这个式子做，要枚举 $x$ （ $T$ 个）并对每个 $x$ 扫过所有奶牛（ $N$ 头），复杂度 $O(N \cdot T)$ 。 $N = 25000$ 、 $T = 10^6$ 时约 $2.5 \times 10^{10}$ ，太慢。瓶颈不在状态定义，而在"每个 $x$ 都重新枚举一遍所有牛"。

观察一：反过来按奶牛转移

$dp[x]$ 的定义只关心两件事：已经铺满的前缀，和最后一头牛。所以反过来按奶牛来推：一头牛 $[l, r]$ 被选中时，它可以接在任意一个"已经铺满到 $p$ "的方案后面，只要 $p \geqslant l - 1$ （ $p = l - 1$ 表示这头牛独立接上； $p > l - 1$ 表示与前面的牛有重叠，重叠是合法的）。

于是每头牛只需要做一次更新：

dp[\min(r, T)] \leftarrow \min\Bigl(dp[\min(r, T)],\; \min_{p \in [\,l - 1,\; \min(r, T)\,]} dp[p] + 1\Bigr).

$r > T$ 的部分对覆盖 $[1, T]$ 没有贡献，所以右端点截断到 $T$ 。每头牛一次"区间最小值查询 + 单点取 min"，总共只有 $N$ 次。

观察二：按右端点升序，来源一定已经就绪

上面的窗口 $[l-1, \min(r,T)]$ 里可能有下标 $p > l-1$ ，也就是"更早的牛已经铺到了 $p$ "。这就要求这些 $dp[p]$ 在处理当前牛之前算好。只要按右端点 $r$ 从小到大处理，每处理完一头牛立刻写入 $dp[\min(r,T)]$ ，那么任何 $p \leqslant r$ 的位置要么是初始的 $dp[0]$ ，要么在更早的轮次已经确定。

更强的理由是：一头牛只写「自己右端点」对应的那个下标，右端点更大的牛写的位置一定 $> r$ ，所以处理到 $r$ 时下标 $\leqslant r$ 的 $dp$ 值再也不会被改动，窗口里的值全是最终值，不会漏解。

观察三：同一个右端点只留最靠左的牛

固定 $r$ ，若有两头牛 $[l_1, r]$ 与 $[l_2, r]$ 且 $l_1 < l_2 \leqslant r$ ，则 $[l_2, r] \subseteq [l_1, r]$ ，两者的转移窗口分别是 $[l_1 - 1, r]$ 与 $[l_2 - 1, r]$ ，前者包含后者，因此

\min_{p \in [l_1 - 1,\, r]} dp[p] \;\leqslant\; \min_{p \in [l_2 - 1,\, r]} dp[p].

用 $[l_1, r]$ 替换 $[l_2, r]$ 既不会更贵，覆盖率也不会变差。所以每个右端点只需保留最小的 $l$ ，转移条数降到 $\min(N, T)$ 以内。顺带两个小剪枝： $l > T$ 的牛一个班次都盖不到，直接丢弃； $r > T$ 的牛右端点截断成 $T$ ，与别的右端点截断后相同的牛一起合并。

样例推演

样例为 $N = 3$ 、 $T = 10$ ，三头牛是 $[1,7]$ 、 $[3,6]$ 、 $[6,10]$ 。下表把班次轴画成表格， ✅ 表示这头牛覆盖该班次，★ 标记最终选中的两头牛。

班次	1	2	3	4	5	6	7	8	9	10
牛1 $[1,7]$ ★	✅	✅	✅	✅	✅	✅	✅
牛2 $[3,6]$			✅	✅	✅	✅
牛3 $[6,10]$ ★						✅	✅	✅	✅	✅
是否被覆盖	✅	✅	✅	✅	✅	✅	✅	✅	✅	✅

牛2 $[3,6]$ 完全落在牛1 $[1,7]$ 内部，选它只会更贵（它的右端点与别人都不同，不会被「同右端点合并」这条规则消掉，但在最优解里它没有位置）。牛1 和牛3 在班次 6、7 重叠，正好把 $[1,10]$ 连成一片，所以答案是 2。

按右端点升序处理时的快照如下（ $+\infty$ 表示该前缀还铺不满）：

处理	$dp[0..10]$	窗口	窗口最小值	结论
牛2 $[3,6]$	$0, +\infty \times 10$	$dp[2..6]$	$+\infty$	前面第 1、2 班次还铺不满，这头牛接不上，跳过
牛1 $[1,7]$	$0, +\infty \times 6, dp[7]=1, +\infty \times 3$	$dp[0..7]$	$0$	$dp[7] \leftarrow 1$
牛3 $[6,10]$	$0, +\infty \times 6, dp[7]=1, +\infty \times 3$	$dp[5..10]$	$1$	$dp[10] \leftarrow 2$

注意第一行：虽然牛2 的右端点最小、最先被处理，但它的窗口里没有任何可达状态，所以被正确跳过——这正说明"来源必须已就绪"这一条件由升序 + 窗口共同保证。

线段树

剩下的就是支持两种操作的数据结构：

查询区间 $[l-1, \min(r,T)]$ 的最小值；
单点 $p$ 与一个值取 min。

这是线段树的标准用法，单次都是 $O(\log T)$ ，也就是常说的"线段树优化 DP"。叶子数取 $T+2$ 是为了让 $dp$ 的下标 $0 \dots T$ 都落在树里（ $0$ 是状态而不是哨兵）。

实现上把这两件事拆成了两个工具函数：push_min 负责"单点取 min 并向上维护"， range_min 负责"查询左闭右开区间的最小值"；主循环 min_cows 里 left_of 是按右端点合并后的字典，covered 就是 $\min(r, T)$ ，prev 就是窗口最小值。

最终答案就是 $dp[T]$ ；它仍是 $+\infty$ 时输出 -1。

代码

cpp

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85/**
 * 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-10-10 11:30
 * update_at: 2026-10-10 11:30
 */
// 清理班次：按右端点升序的 DP，线段树维护 dp 的区间最小值。
#include <cstdio>
#include <map>
#include <vector>

typedef long long ll;

const ll INF = 1000000000LL; // 不可达哨兵：答案最多 N，与真实值不会混淆

std::vector<ll> tree;
ll seg_size;

// 把叶子 pos 的值与 value 取 min，并向上维护区间最小值
void push_min(ll pos, ll value) {
    ll i = seg_size + pos;
    if (tree[i] <= value) return;
    tree[i] = value;
    i >>= 1;
    while (i) {
        ll merged = tree[i << 1] < tree[i << 1 | 1] ? tree[i << 1] : tree[i << 1 | 1];
        if (tree[i] == merged) break; // 本节点没变，祖先自然也不会变
        tree[i] = merged;
        i >>= 1;
    }
}

// 查询下标区间 [left, right) 的最小值
ll range_min(ll left, ll right) {
    ll res = INF;
    left += seg_size;
    right += seg_size;
    while (left < right) {
        if (left & 1) {
            if (tree[left] < res) res = tree[left];
            left++;
        }
        if (right & 1) {
            right--;
            if (tree[right] < res) res = tree[right];
        }
        left >>= 1;
        right >>= 1;
    }
    return res;
}

int main() {
    ll n, T;
    if (scanf("%lld %lld", &n, &T) != 2) return 0; // 空输入安全返回

    // 右端点相同的牛只留左端点最靠左的那头，其余都被它完全支配
    std::map<ll, ll> left_of;
    for (ll i = 0; i < n; i++) {
        ll left, right;
        scanf("%lld %lld", &left, &right);
        if (left <= T) { // 一个班次都盖不到的牛直接丢弃
            std::map<ll, ll>::iterator it = left_of.find(right);
            if (it == left_of.end()) left_of[right] = left;
            else if (left < it->second) it->second = left;
        }
    }

    seg_size = 1;
    while (seg_size < T + 2) seg_size <<= 1; // dp 下标是 0..T
    tree.assign(seg_size << 1, INF);
    push_min(0, 0); // dp[0] = 0：还没铺任何班次

    for (std::map<ll, ll>::iterator it = left_of.begin(); it != left_of.end(); ++it) {
        ll right = it->first, left = it->second;
        ll covered = right < T ? right : T; // 覆盖到 T 之后再多的班次没有意义
        ll prev = range_min(left - 1, covered + 1);
        if (prev < INF) push_min(covered, prev + 1);
    }

    ll ans = range_min(T, T + 1);
    printf("%lld\n", ans < INF ? ans : -1);
    return 0;
}

python

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83#!/usr/bin/env python3
# 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-10-01 21:34
# update_at: 2026-10-01 21:45

import sys

INF = 10 ** 9  # 不可达哨兵：答案最多 N = 25000，与真实值不会混淆


def push_min(tree: list[int], size: int, pos: int, value: int) -> None:
    """把叶子 pos 的值与 value 取 min，并向上维护区间最小值。"""
    i = size + pos
    if tree[i] <= value:
        return
    tree[i] = value
    i >>= 1
    while i:
        merged = min(tree[i << 1], tree[i << 1 | 1])
        if tree[i] == merged:  # 本节点没变，祖先自然也不会变
            break
        tree[i] = merged
        i >>= 1


def range_min(tree: list[int], size: int, left: int, right: int) -> int:
    """查询下标区间 [left, right) 的最小值。"""
    res = INF
    left += size
    right += size
    while left < right:
        if left & 1:
            res = min(res, tree[left])
            left += 1
        if right & 1:
            right -= 1
            res = min(res, tree[right])
        left >>= 1
        right >>= 1
    return res


def min_cows(left_of: dict[int, int], T: int) -> int:
    """返回铺满班次 1..T 的最少奶牛数，不可达时返回 INF。

    left_of[r] 是所有右端点为 r 的牛里最小的左端点。按右端点升序处理，
    一头牛 [l, r] 能接在任意一个"已铺满到 p"的方案后面（p >= l-1，重叠合法），
    所以每次只需查一次 dp[l-1 .. min(r,T)] 的最小值，再更新 dp[min(r,T)]。
    """
    size = 1
    while size < T + 2:  # dp 下标是 0..T，加 2 保证叶子数够用且是 2 的幂
        size <<= 1
    tree = [INF] * (size << 1)
    push_min(tree, size, 0, 0)  # dp[0] = 0：还没铺任何班次

    for right, left in sorted(left_of.items()):
        covered = min(right, T)  # 覆盖到 T 之后再多的班次没有意义
        prev = range_min(tree, size, left - 1, covered + 1)
        if prev < INF:  # 前面那段铺不满，这头牛接不上任何方案
            push_min(tree, size, covered, prev + 1)

    return range_min(tree, size, T, T + 1)  # 答案就是 dp[T]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, T = next(data), next(data)

    # 右端点相同的牛只留左端点最靠左的那头，其余都被它完全支配
    left_of: dict[int, int] = {}
    for _ in range(n):
        left, right = next(data), next(data)
        if left <= T:  # 一个班次都盖不到的牛直接丢弃
            left_of[right] = min(left_of.get(right, T + 1), left)

    ans = min_cows(left_of, T)
    print(ans if ans < INF else -1)


if __name__ == "__main__":
    solve()

复杂度

时间：排序 $O(N \log N)$ ，每头牛一次查询一次更新，各 $O(\log T)$ ，合计 $O(N \log N + N \log T)$ 。
空间：线段树 $O(T)$ ，合并右端点的字典 $O(N)$ ，合计 $O(N + T)$ 。

总结

模型是"最小区间覆盖"，状态 $dp[x]$ 取"铺满前缀 $1 \dots x$ "。
关键变化是从按班次枚举改成按奶牛枚举：每头牛只贡献一次"区间最小值查询 + 单点取 min"。
两个化简让更新次数降到 $N$ 级别：按右端点升序保证来源就绪；同右端点只留最靠左的牛。
用线段树把每次区间查询压到 $O(\log T)$ ，整体 $O(N \log N + N \log T)$ 。
无解的判定很自然： $dp[T]$ 从未被更新（仍是 $+\infty$ ）就输出 -1，不需要额外特判。

补充：区间覆盖的经典贪心（每次在 $l_i \leqslant pos$ 的牛里选 $r_i$ 最大的）也能求出同样的最小值，但它无法解释上面这个转移式，也容易在"空隙"上写错，因此这里不作为主解。

图示解析

这张图串起本题从建模到得到答案的主线：

text

1
2
3
4
5
6输入：若干牛，每头牛是一个区间 [l, r]
`- 目标：用最少的区间盖满 1..T
   |- 形式化：dp[x] = 铺满 1..x 的最少奶牛数
   |  `- dp[r] <- min(dp[l-1 .. r]) + 1（每个右端点只有最优的那个 l 有用）
   `- 加速：按右端点升序，把"区间取 min + 单点 chmin"交给线段树
      `- 答案 dp[T]；仍是 +∞ 说明盖不满，输出 -1

先看每个节点代表的推理结论：区间覆盖 → 一维 DP → 转移只依赖一段区间最小值 → 线段树把朴素的 $O(N \cdot T)$ 转移降到 $O(N \log T)$ 。图中只保留正文已经证明过的关键关系，不替代正文中的样例推演和正确性说明。