[USACO06FEB] Stall Reservations S

形式化题目

给定 $N$ 个闭区间 $[A_i,B_i]$ ，要把每个区间分配到某个牛棚中。一个分配方案合法，当且仅当同一个牛棚内的任意两个区间都没有公共时刻，即闭区间意义下两两不相交。求最少需要多少个牛棚，并给出每个区间分到的牛棚编号。

题目只保证牛棚数最少、分配合法，具体编号不唯一（特殊评测）。

样例里 5 头牛在时间轴上的覆盖如下。每一列是一个时刻，有 $\checkmark$ 表示这头牛此刻正在挤奶。

时刻	1	2	3	4	5	6	7	8	9	10
牛1 `[1,10]`	✓	✓	✓	✓	✓	✓	✓	✓	✓	✓
牛2 `[2,4]`		✓	✓	✓
牛3 `[3,6]`			✓	✓	✓	✓
牛4 `[5,8]`					✓	✓	✓	✓
牛5 `[4,7]`				✓	✓	✓	✓
同时在棚的牛数	1	2	3	4	4	4	3	2	1	1

时刻 $4$ 到 $6$ 同时有 $4$ 头牛在挤奶，它们必然要占 $4$ 个不同的棚，所以答案不可能小于 $4$ ；这个样例的最少棚数正是 $4$ 。一般地，最少牛棚数等于"某一时刻同时在挤奶的牛数"的历史最大值，这一点在正解里会给出证明。

暴力解法

思路

把"每头牛进哪个棚"直接看成一串选择，逐头牛决定。按开始时间顺序处理第 $dep$ 头牛时：

它可以放进任意一个已经开好、且当前的牛不会和它冲突的棚；
也可以另外新开一个棚。

用 choose[id] 记录当前方案里每头牛去的棚，stall_end[k] 记录第 $k$ 个棚最后一头牛的结束时间。dfs(dep, used) 枚举第 $dep$ 头牛的所有放法，递归到 dep == N+1 时所有牛都安排好了，就用 used（开了几个棚）更新最少棚数并保存方案。

因为每一头牛都把"放进哪个棚"的所有可能都试了一遍，所有合法分配都会被枚举到，所以叶子节点里取到的最小 used 就是真正的最少棚数。brute.cpp 里还有一句 if (used >= best_cnt) return;：当前已经开了不少于最优解的棚数，再往下不可能更优，可以提前剪掉。

代码

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
86
87
88
89
90
91/**
 * 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-09-27 16:30
 * update_at: 2026-09-27 16:31
 */
// brute.cpp：小数据暴力解，枚举每头牛放进哪个牛棚，找出最少牛棚数。
// 每层递归依次处理第 dep 头牛，选择它可以放进哪一个已经开了的棚，或者新开一个棚。
// 只适合 n 很小的情况（指数级），用来帮助理解题意并和 main.cpp 对拍。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int MAXN = 15;

int n;

struct Cow {
    int l;
    int r;
    int id; // 输入顺序
};
Cow cow[MAXN];

int stall_end[MAXN]; // stall_end[k] 表示第 k 个牛棚当前最后一头牛的结束时间
int choose[MAXN];    // choose[id] 表示第 id 头牛当前方案里去的牛棚编号
int best_ans[MAXN];  // 最优方案里每头牛去的牛棚编号
int best_cnt;        // 最优方案用了几个棚

// 按开始时间从小到大排序，先处理开始早的牛
bool cmp_cow(const Cow &a, const Cow &b) {
    if (a.l != b.l) return a.l < b.l;
    return a.r < b.r;
}

// dep：当前处理到第几头牛；used：当前已经开了几个棚
void dfs(int dep, int used) {
    // 已经不可能比当前最优解更好了，剪枝
    if (used >= best_cnt) return;

    if (dep == n + 1) {
        // 走到这里说明所有牛都安排好了，更新最优解
        best_cnt = used;
        for (int i = 1; i <= n; i++) {
            best_ans[i] = choose[i];
        }
        return;
    }

    // 尝试放进已经开好的某个棚（端点也算占用，要严格小于才开始）
    for (int k = 1; k <= used; k++) {
        if (stall_end[k] < cow[dep].l) {
            int old = stall_end[k];
            stall_end[k] = cow[dep].r;
            choose[cow[dep].id] = k;
            dfs(dep + 1, used);
            stall_end[k] = old; // 恢复现场
        }
    }

    // 或者为这头牛新开一个棚
    stall_end[used + 1] = cow[dep].r;
    choose[cow[dep].id] = used + 1;
    dfs(dep + 1, used + 1);
    stall_end[used + 1] = 0; // 恢复现场
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> cow[i].l >> cow[i].r;
        cow[i].id = i;
    }

    sort(cow + 1, cow + 1 + n, cmp_cow);

    best_cnt = n + 1; // 初始化为一个一定更差的上界
    dfs(1, 0);

    cout << best_cnt << "\n";
    for (int i = 1; i <= n; i++) {
        cout << best_ans[i] << "\n";
    }

    return 0;
}

复杂度

时间：每头牛可选"已开的棚或新开一个"，分支数随深度增长，上界是 $O(N^N)$ 级别，实际只适合 $N \leqslant 8$ 左右。
空间：choose、stall_end 等均为 $O(N)$ 。

瓶颈

暴力的低效来自把"放进哪个棚"当成完全自由的选择，于是必须试遍所有棚。但一个棚的状态其实只有一个数有用：它当前最后一头牛的结束时间。而且判断"还有没有空棚"也不需要逐个检查，只要看最早空出的那个棚——它都没空，别的棚更不可能空。抓住这两点，就不必枚举全部放法。

正解

关键观察

一、按开始时间排序，逐头处理。 把牛按 $A_i$ 升序排序后依次安排。处理当前牛时，之前所有牛都已经放好，它的左端点不小于之前任何一头。

二、一个棚能否复用，只看它当前占用到什么时候。 当前牛是 $[A,B]$ ，某棚最后一头牛是 $[A',B']$ 。因为是闭区间，只要 $B' \geqslant A$ ，两头牛就会在时刻 $\max(A,A')$ 撞上，不能同棚。所以能复用的条件是 $B' < A$ ，是严格小于。

三、最早空出的棚决定有没有空棚。 把所有已开棚按"当前结束时间"放进一个小根堆，堆顶就是最早空出的棚。若堆顶都满足 结束时间 >= A，说明所有棚都还占着，只能新开；否则直接弹出堆顶复用。棚与棚之间完全等价，复用哪个空棚都不影响结果，所以复用堆顶即可。

有了这三点，每头牛只做一次"看堆顶"的判断，不需要回头枚举。

贪心用的就是最少棚数

设贪心第 $k$ 次被迫新开棚，此时当前牛的开始时间是 $A$ 。前面 $k-1$ 个棚各有一头"最后一头牛"，它们的开始时间都 $\leqslant A$ （排序保证），结束时间都 $\geqslant A$ （否则堆顶会空出来，不会被迫新开），所以这 $k-1$ 头牛连同当前这头牛，共 $k$ 头牛在时刻 $A$ 同时挤奶，必须占用 $k$ 个不同的棚。于是最优解的棚数 $\geqslant$ 某时刻同时挤奶的牛数 $\geqslant k$ 。而贪心总共只用了 $k$ 个棚，两边合起来就得到"贪心棚数 $=$ 最少棚数"。

这也顺带证明了前面那句话：最少棚数就等于同时挤奶牛数的最大值。

思路

读入时记下每头牛的原始编号，按左端点 $A$ 升序排序（ $A$ 相同则按右端点）。
维护一个小根堆，每个元素是一个牛棚：编号 id 和它当前最后一头牛的结束时间 cow。
依次处理每头牛 $[A,B]$ ：
- 堆非空且堆顶的 cow < A：弹出堆顶，把这头牛放进这个棚，把该棚的 cow 改成 $B$ 再压回堆；
- 否则：新开一个棚 cnt++，把 (cnt, B) 压入堆。
答案就是最后的 cnt；按原始编号输出每头牛的棚号。

样例的贪心过程如下表。每一步都只比较"堆顶的结束时间"和当前牛的开始时间。

处理顺序	牛（输入编号）	区间	堆顶（最早空出的棚）	决策
1	牛1	`[1,10]`	堆空	新开棚1
2	牛2	`[2,4]`	棚1 结束 $10 \geqslant 2$	新开棚2
3	牛3	`[3,6]`	棚2 结束 $4 \geqslant 3$	新开棚3
4	牛5	`[4,7]`	棚2 结束 $4 \geqslant 4$	新开棚4
5	牛4	`[5,8]`	棚2 结束 $4 < 5$	复用棚2

第 4 步是本题最容易错的地方： $[4,7]$ 和棚2里的 $[2,4]$ 在时刻 $4$ 相撞，因为端点也算占用，所以 4 >= 4 判定为没空，必须新开棚。最终分配是牛1→棚1、牛2→棚2、牛3→棚3、牛4→棚2、牛5→棚4，与样例输出一致。

代码

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
86
87
88
89
90
91
92/**
 * 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-09-27 16:30
 * update_at: 2026-09-27 16:31
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int MAXN = 50005;

int n;
int ans[MAXN]; // ans[i] 表示第 i 头牛被分到的牛棚编号

// 一头牛：挤奶区间 [l, r]，id 是输入顺序
struct Cow {
    int l;
    int r;
    int id;
};
Cow cow[MAXN];

// 按挤奶开始时间从小到大排序；开始时间相同则结束早的排前面
bool cmp_cow(const Cow &a, const Cow &b) {
    if (a.l != b.l) return a.l < b.l;
    return a.r < b.r;
}

// 牛棚：id 是编号，cow 是这个棚当前最后一头牛的结束时间
struct Node {
    int id;
    int cow;
    // priority_queue 默认是大根堆，重载 < 让结束时间早的排在堆顶
    bool operator<(const Node &b) const {
        return cow > b.cow;
    }
};
priority_queue<Node> pq; // 小根堆，堆顶是“最快空出来”的牛棚

void read_data() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> cow[i].l >> cow[i].r;
        cow[i].id = i;
    }
}

void solve() {
    sort(cow + 1, cow + 1 + n, cmp_cow);

    int cnt = 0; // 当前已经启用的牛棚数，也就是最少牛棚数
    for (int i = 1; i <= n; i++) {
        int l = cow[i].l;
        int r = cow[i].r;
        int id = cow[i].id;

        // 区间端点也算使用时间，所以必须堆顶的结束时间严格小于 l 才能复用
        if (!pq.empty() && pq.top().cow < l) {
            Node t = pq.top();
            pq.pop();
            ans[id] = t.id; // 复用这个最早空出来的棚
            t.cow = r;      // 它的占用时间更新为当前这头牛
            pq.push(t);
        } else {
            // 所有已开的棚都还没空，只能新开一个
            cnt++;
            Node t;
            t.id = cnt;
            t.cow = r;
            ans[id] = cnt;
            pq.push(t);
        }
    }

    cout << cnt << "\n";
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    read_data();
    solve();

    return 0;
}

同目录下的 main.py 是同一套贪心的 Python 实现，用 heapq 存 (结束时间, 棚号)。

复杂度

时间：排序 $O(N\log N)$ ，每头牛最多一次堆弹出和一次堆压入，各 $O(\log N)$ ，总计 $O(N\log N)$ 。
空间：堆、排序数组、答案数组均为 $O(N)$ 。

总结

模型：把牛看成闭区间，同棚区间两两不相交；求区间划分的最少组数。
贪心：按开始时间排序，用小根堆维护各棚"最后占用的结束时间"，堆顶能空出来（严格小于当前左端点）就复用，否则新开棚。
为什么对：每次被迫新开第 $k$ 个棚时，有 $k$ 头牛同时挤奶，必须 $k$ 个棚，这是下界；贪心恰好只用 $k$ 个棚，因此最优。
易错点：复用条件必须是 结束时间 < 开始时间（严格小于），因为区间端点也算占用；输出要按输入顺序，所以读入时要存原始编号。
一句话记忆：最少棚数 = 同时挤奶牛数的最大值；用堆只维护"最早空出的棚"，就能在线求出这个最大值。