畜栏分配问题

题目描述

有 $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

输入 #1

5
1 10
2 4
3 6
5 8
4 7

输出 #1

4
1
2
3
2
4

输入输出样例 #2

输入 #2

3
1 3
2 4
5 6

输出 #2

2
1
2
1

限制条件

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

样例解释 #1

有 5 头牛：

1. 牛 1：吃草时间 $[1, 10]$
2. 牛 2：吃草时间 $[2, 4]$
3. 牛 3：吃草时间 $[3, 6]$
4. 牛 4：吃草时间 $[5, 8]$
5. 牛 5：吃草时间 $[4, 7]$

安排方案：

• 畜栏 1：牛 1
• 畜栏 2：牛 2 和牛 4（时间不重叠：$[2,4]$ 和 $[5,8]$）
• 畜栏 3：牛 3
• 畜栏 4：牛 5

需要至少 4 个畜栏。

解题思路

这是一个典型的活动安排问题，可以使用贪心算法解决：

1. 将所有牛按照开始吃草时间 $A$ 从小到大排序
2. 维护一个最小堆，存储当前所有畜栏中最后一头牛的结束时间以及畜栏编号
3. 遍历排序后的牛：
   • 如果当前堆为空，或者堆顶（最早结束的畜栏）的结束时间 $\ge$ 当前牛的开始时间，说明需要新开一个畜栏
   • 否则，可以将当前牛安排到堆顶的畜栏，并更新该畜栏的结束时间为当前牛的结束时间
4. 最后堆的大小就是所需的最小畜栏数

这种方法的正确性基于贪心策略：总是将牛安排到最早结束的可用畜栏中，这样可以最大化畜栏的利用率。