区间分组证明

区间分组证明（区间图着色）

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

为了解决“畜栏预定”问题，我们可以采用一种贪心策略。该策略的正确性可以通过将其与区间图的着色问题联系起来进行证明。

核心思想

模型转换：将每头牛的吃草时间段 [A, B] 看作数轴上的一个区间。如果两个区间相交，则对应的两头牛不能使用同一个畜栏。这完全等价于图论中的区间图着色问题。我们为每个区间创建一个顶点，如果两个区间相交，就在对应的顶点之间连一条边。问题的目标是用最少的颜色给图的所有顶点着色，使得任意两个相邻的顶点颜色都不同。所需的最小颜色数称为图的色数 (Chromatic Number)。
区间图性质：对于区间图，其色数等于其最大团 (Maximum Clique) 的大小。一个“团”是指图中的一个顶点子集，其中任意两个顶点之间都存在边。在我们的问题中，一个团就对应一组两两相交的区间。因此，最大团的大小就等于在某个时间点上，同时重叠的区间的最大数量。
贪心策略：
- 将所有区间按左端点（开始时间）从小到大排序。
- 顺序遍历排序后的区间，对于每个区间，尝试将其放入一个现有的、可以容纳它的畜栏中。一个畜栏可以容纳当前区间，当且仅当该畜栏中最后一个区间的结束时间早于当前区间的开始时间。
- 如果有多个畜栏可用，我们选择那个结束时间最早的畜栏（这样可以尽早空闲出来给后续的区间使用）。这可以通过维护一个存储各畜栏结束时间的小根堆来高效实现。
- 如果没有畜栏可用，则必须分配一个新的畜栏。

正确性证明

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

假设贪心算法最终使用了 $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$ 个畜栏。因此，我们的算法得到的就是最优解。