畜栏预定

1 题目描述

有 $N$ 头牛在畜栏中吃草。

每个畜栏在同一时间段只能提供给一头牛吃草，所以可能会需要多个畜栏。

给定 $N$ 头牛和每头牛开始吃草的时间 $A$ 以及结束吃草的时间 $B$，每头牛在 $[A, B]$ 这一时间段内都会一直吃草。

当两头牛的吃草区间存在交集时（包括端点），这两头牛不能被安排在同一个畜栏吃草。

求需要的最小畜栏数目和每头牛对应的畜栏方案。

输入格式

第 1 行：输入一个整数 $N$。

第 2…N+1 行：第 $i+1$ 行输入第 $i$ 头牛的开始吃草时间 $A$ 以及结束吃草时间 $B$，数之间用空格隔开。

输出格式

第 1 行：输入一个整数，代表所需最小畜栏数。

第 2…N+1 行：第 $i+1$ 行输入第 $i$ 头牛被安排到的畜栏编号，编号是从 1 开始的连续整数，只要方案合法即可。

数据范围

$1 \le N \le 50000$, $1 \le A, B \le 1000000$。

输入样例：

1
2
3
4
5
6

5
1 10
2 4
3 6
5 8
4 7

输出样例：

1
2
3
4
5
6

4
1
2
3
2
4

2 解析

区间分组 的板子。

启发式策略：

1. 区间按左端点升序枚举。
2. 如果之前 存在 一个组的区间右端点不与当前区间左端点相交，则将当前区间插入该组。
3. 如果之前 不存在 一个组的区间右端点不与当前区间左端点相交，则开一个新的分组存放当前区间。

反证法，假设最优解的区间组数是 $m$。

考虑在上述做法中，设第一次新建第 $m+1$ 个组的时刻，是在处理第 $i$ 个区间。

由于所有区间是按左端点升序排序，所以现在前 $m$ 个组中最后一个区间的左端点一定小于等于第 $i$ 个区间的左端点。

且前 $m$ 个组中最小的右端点大于等于第 $i$ 个区间的左端点，所以前 $m$ 个组里最后一个区间一定都包含第 $i$ 个区间的左端点，所以我们就找到了 $m+1$ 个区间存在交集，所以至少需要 $m+1$ 个畜栏，矛盾。

我的证明: 设前 $i$ 个区间的最优解为 $m$（分解问题），那么第 $i+1$ 个区间，如果与前面的区间都有交集，那么最优解就是 $m+1$，否则就是 $m$，所以贪心策略是正确的。
见下文区间图着色的证明

做法：用一个小根堆来维护所有组的右端点，以此来判断是否存在一个组的区间右端点不与当前区间左端点相交。

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

sort(seg + 1, seg + n + 1);
priority_queue<PII, vector<PII>, greater<PII>> heap;
for (int i = 1; i <= n; i ++ )
{
    if (heap.empty() || heap.top().x >= seg[i].l)
    {
        res[seg[i].id] = heap.size() + 1;
        heap.push({seg[i].r, heap.size() + 1});
    }
    else
    {
        int t = heap.top().y;
        heap.pop();
        res[seg[i].id] = t;
        heap.push({seg[i].r, t});
    }
}

3 区间图着色的证明

这是一个更具数学色彩的证明，它将问题与图论中的区间图着色问题联系起来。

上面的贪心策略为什么正确？把它和区间图的着色问题联系起来就能看清。

3.1 核心思想：转成区间图着色

1. 模型转换：将每头牛的吃草时间段 [A, B] 看作数轴上的一个区间。如果两个区间相交，则对应的两头牛不能使用同一个畜栏。这完全等价于图论中的区间图着色问题。我们为每个区间创建一个顶点，如果两个区间相交，就在对应的顶点之间连一条边。问题的目标是用最少的颜色给图的所有顶点着色，使得任意两个相邻的顶点颜色都不同。所需的最小颜色数称为图的色数 (Chromatic Number)。

2. 区间图性质：对于区间图，其色数等于其最大团 (Maximum Clique) 的大小。一个“团”是指图中的一个顶点子集，其中任意两个顶点之间都存在边。在我们的问题中，一个团就对应一组两两相交的区间。因此，最大团的大小就等于在某个时间点上，同时重叠的区间的最大数量。

3. 贪心策略：

   • 将所有区间按左端点（开始时间）从小到大排序。
   • 顺序遍历排序后的区间，对于每个区间，尝试将其放入一个现有的、可以容纳它的畜栏中。一个畜栏可以容纳当前区间，当且仅当该畜栏中最后一个区间的结束时间早于当前区间的开始时间。
   • 如果有多个畜栏可用，我们选择那个结束时间最早的畜栏（这样可以尽早空闲出来给后续的区间使用）。这可以通过维护一个存储各畜栏结束时间的小根堆来高效实现。
   • 如果没有畜栏可用，则必须分配一个新的畜栏。

3.2 正确性证明

该贪心算法所得的解即为最优解。

假设贪心算法最终使用了 $k$ 个畜栏。这意味着在算法执行过程中，有一个时刻我们不得不创建第 $k$ 个畜栏。让我们分析这个时刻：

• 假设我们正要处理区间 $I$，并且发现所有 $k-1$ 个已有的畜栏都无法容纳它。
• 根据我们的策略，这意味着这 $k-1$ 个畜栏中，每一个畜栏的最后一个区间的结束时间都晚于或等于区间 $I$ 的开始时间 $l(I)$。
• 令这 $k-1$ 个畜栏中最后的区间分别为 $J_1, J_2, \dots, J_{k-1}$。因为我们是按左端点升序处理的，所以这些区间的左端点 $l(J_i)$ 都小于或等于 $l(I)$。
• 因此，在时间点 $l(I)$，我们有 $l(J_i) \le l(I) \le r(J_i)$ 成立（对于所有 $i=1, \dots, k-1$）。
• 这意味着在 $l(I)$ 这个时间点，区间 $I$ 以及 $J_1, \dots, J_{k-1}$ 这 $k$ 个区间都是重叠的。
• 这 $k$ 个区间构成了一个大小为 $k$ 的团（Clique）。根据区间图的性质，任何合法的着色方案都至少需要 $k$ 种颜色。
• 所以，任何合法的畜栏分配方案都至少需要 $k$ 个畜栏。

我们的算法给出了一个使用 $k$ 个畜栏的方案，同时我们证明了最优解至少需要 $k$ 个畜栏。因此，我们的算法得到的就是最优解。

4 相关题解

暂无相关题解