完美图

区间相交表示任务不能共用一份资源，颜色表示资源编号。一次合法染色是把全部任务分配出去；某时刻同时执行的任务则证明至少需要多少资源。如果算法恰好用了这么多份资源，上界和下界就接合成最优性证书。

完美性还要求删掉任意一批任务后，这种配合仍然成立。只计算原始任务集的色数不够：一个局部障碍可能被别处更大的团掩盖。定义中的“每个 $S$”把这个要求写成了可以逐层限制的接口。

从共同交点得到团证书 ​

区间的一个特殊性质是：非空有限族中的区间若都是非空半开区间且两两相交，就必有共同交点。取它们最大的左端点 $t=\underset{i}{max}{s}_i$，并选一个左端点等于 $t$ 的区间 $I_j$。每个 $I_i$ 都与 $I_j$ 相交，所以存在交点 $x\ge t$ 且 $x<f_i$，从而 $t<f_i$；另一方面 $s_i\le t$。因此 $t\in I_i$ 对所有 $i$ 成立。这就是本例所需的一维 Helly 性质。

令最大同时重叠数为

同一时刻的区间两两相交，给出大小为 $\delta$ 的团；反过来，任一团的区间两两相交，刚才的证明给出共同交点。因此 $\omega (G)=\delta$。这一结论依赖区间结构，不能从任意交集图的“两两相交”直接推出“共同相交”。

最早开始、最早释放的资源分配 ​

按左端点从小到大处理区间，同左端点可任意排序。维护一个最小堆，每份已建立的资源恰有一项 $(\text{最后任务的结束时刻},\text{资源编号})$。处理 $[s,f)$ 时，若堆为空便新建资源；否则查看堆顶结束时刻 $r$。当 $r\le s$ 时，取出堆顶，把新区间接到该资源上，并放回结束时刻 $f$；当 $r>s$ 时，新建一份资源并入堆。同结束时刻可按编号打破平局。

这个贪心算法公理库贪心算法Greedy algorithm每一步作局部最优且不回溯选择的算法设计范式。始终给出合法染色：同一资源上的前一区间在新区间开始前或开始时已结束。如果算法首次建立第 $d$ 份资源，堆中原有每份资源的最后任务都满足结束时刻大于当前左端点 $s$，而它们的开始时刻不晚于 $s$。这些 $d-1$ 个区间与当前区间共同包含 $s$，构成一个 $d$ 团。因此开出第 $d$ 份资源的动作本身就给出 $\chi (G)\ge d$ 的证书；最终的 $d$ 色分配又给出 $\chi (G)\le d$。于是

现在取任意 $S\subseteq V$。只留下 $S$ 对应的区间时，任意两个剩余区间的相交关系都不变，得到的正是 $G[S]$。对这个子区间族重做上述论证，便有 $\chi (G[S])=\omega (G[S])$；空子族也满足零等式。这一步才把整图最优染色提升为区间图的完美性证明。原染色直接限制到子族虽然合法，却未必仍最优，必要时应重新运行算法。

六个区间的完整运行 ​

取

下面把堆内容按键值顺序列出；这是便于核验的有序表示，并非堆的内部数组布局。

结果为三组 $\{A,E\}$、$\{B,D\}$、$\{C,F\}$。在 $t=2$ 时，$A,B,C$ 同时存在，形成三团，所以三份资源已经最少。$t=3$ 时 $B$ 已结束，$D$ 才能接入资源 $2$；在 $t=6$ 时资源 $2$ 也已释放，但资源 $3$ 的最后结束时刻更小，所以堆顶规则把 $F$ 分给资源 $3$。

等式和删边的两条边界 ​

五圈 $C_5$ 无三角形而有边，故 $\omega (C_5)=2$；沿圈交替使用两色会在闭合处冲突，三色则可行，故 $\chi (C_5)=3$。因此它不是完美图。更隐蔽的反例是互不连接的 $K_3$ 与 $C_5$：两个分量可以复用颜色，整图色数为三，最大团也为三，然而只取五圈的顶点便得到一个不满足等式的诱导子图。整图的 $\chi =\omega$ 不是完美性的充分条件。

完美性在诱导子图下保持，却不在任意删边下保持。$K_5$ 的每个诱导子图都是完全图，因而完美；只保留一条五圈的五条边、删除其余弦，得到的 $C_5$ 就不完美。不能把定义中的“诱导”省掉。

给定区间端点，排序需 $O(n\log n)$ 时间；若最终使用 $d$ 份资源，堆处理需 $O(n\log (d+1))$ 时间，堆占 $O(d)$ 空间，保存全部分配结果另需 $O(n)$ 空间。算法不必显式生成可能含有二次数量边的冲突图。这里的保证使用左端点排序；它没有声称任意到达顺序下、不允许改色的在线贪心都能最优。

区间分配与“选择尽可能多的互不重叠区间”有不同目标。后者可以舍弃任务，通常按结束时刻选择；本页必须安排全部任务，优化的是资源数，所以按开始时刻处理。两种规则各自依赖自己的最优性证明。

同一实例也把Dilworth 定理公理库Dilworth 定理Dilworth's theorem有限偏序集的最大反链大小等于覆盖全部元素所需的最少链数。变成了可直接核验的链与反链证书。在区间集合上定义严格次序

非空区间使这个关系反自反；若 $x<y<z$，则 $f_x\le s_y<f_y\le s_z$，所以关系传递，加上相等关系便得到偏序。两个不同元素不可比较，当且仅当对应区间相交。因此区间图是这个偏序的不可比较图：同色独立集对应链，团对应反链，而不是把可比较的元素连接成边。在六区间实例中，三条链 $A<E$、$B<D$、$C<F$ 与三元素反链 $\{A,B,C\}$ 达到 Dilworth 等式的两端。算法还给出了这类偏序不经通用匹配求解便能获得最优链分割的办法。

一般有限偏序的不可比较图同样完美：在任意元素子集上，色数是最少链分割数，团数是最大反链大小，Dilworth 定理使两者相等。区间证明额外提供了共同交点和堆算法；它不意味着任意完美图都能套用这条区间扫描规则。