区间图：贪心直接最优
一天 9 场会，最少要几间会议室。把每场会画成时间轴上的一个区间、撞期的两场会连一条边，得到的冲突图结构极好，最优的房间数可以被一个初等算法直接拿到。本页先证明这条最优性，再展示它对处理顺序的依赖：一句听上去有理的调度经验，就能把同一批会多排进一间房。
1 · 会议与冲突图
样本日程是 9:00–18:00 的 9 场会，从早上的站会到傍晚的规划。顶点是会，边是撞期，两个区间相交即相邻，这样得到的冲突图称为区间图 (interval graph)。这份日程的区间图有 9 个顶点、7 条边。
房间数有一个不需要图论的下界：某一时刻有 场会同时进行，这 场会两两撞期，至少要 间房。沿时间轴做扫描线 (sweep line)，起点计 、终点计 ，累计值的峰值就是最大同时进行数；同时进行的会在冲突图里两两相邻、构成团，峰值即最大团规模 。这份日程的峰值是 3，周会、面试与评审在上午三场并行。
按开始时间从早到晚处理，每场会取「与它撞期的已分配会」没占用的最小房号，9 场会恰好排进 3 间房，撞上下界。这不是这份日程的巧合。
2 · 开始时间序的最优性
定理 2.1 区间图上按开始时间做贪心着色（逐场会取最小空闲房号），使用的房间数恰为最大同时进行数 。
证明 设贪心共开 间房，考察第 间房第一次被打开的时刻，即某场会 分到 号房的那一步。此刻前 间房都被与 撞期的会占着；按开始时间序，这些会开始得不比 晚，又与 相交，于是在 开始的瞬间它们全部正在进行，连同 共 场同时，故 。反向由 §1 的下界给出：任何可行分配至少用 间房。∎
两端在同一时刻碰头：区间图上 ，一般图 NP-hard 的色数计算塌成一次 的排序。
注 · 区间图是完美图的一员。完美图 (perfect graph) 要求每个导出子图都满足 ，区间图、二部图、弦图都在其中；完整刻画与强完美图定理见着色：顶点、边、列表与完美图的 perfect graph 注记。
3 · 时长降序的反例
定理 2.1 的证明里，「开始时间」只在一处出场：新房打开时，占着旧房的会必须全部正在进行。换一个顺序，这一环就断了，而候选顺序里最有迷惑性的是那句调度直觉「长会难排，先排长会」。
长会反例的 5 场会戳破这句经验：峰值只有 2，按开始时间贪心开 2 间房，按时长降序贪心却开 3 间。机制在冲突图上一目了然。这 5 场会的冲突图是一条 5 个点的路 ，4 条边，，站会、周会、面试、评审、培训依次相连。时长降序的前两位是培训与周会，两者不撞期，同进 1 号房，而它们正好是「周会–面试–评审–培训」这条链的两端；评审随后与培训撞期，进 2 号房；轮到面试，两侧的周会与评审已分别占住 1、2 号房，只好开出第 3 间。这与皇冠图坏序同一机理——先给一条路的两端着同色，中间的点就被逼出新色（顶点序的整套实验见顶点序的实验）；不同的是，这一次坏序不是精心构造的排列，而是一份完全现实的日程表加一句排会经验。
构造这份反例走过一段弯路。要让时长降序翻车，冲突图得是一条路，且最长的会落在路的两端，最短的写法是四场首尾相接的链式会议；但「一天只有四场两两相接的会」太做作，于是把 嵌进一份真实的日程，周会、面试、评审、培训依次相接，再加一场只与周会撞期的站会凑成完整的一天。冲突图从 长成 ，反例依旧成立：站会最短，在时长降序里排最后，不碰机制。这条路的点数、边数与 ，连同两种顺序的房数，都锁在引擎的测试断言里。
4 · 随机区间上的验证
定理的证明不依赖任何样本，但样本之外多跑几组更踏实。引擎在 20 组由 seed 生成的随机区间集上逐组核对（每组 10 个区间，起点与时长都随机）：按开始时间贪心的房数与扫描线峰值全部相等，与定理 2.1 一致。
建议 · 现实排会往往带偏好约束。固定房间的例会、按容量分档的大小会议室、指定设备的评审间，都会把「任何房都行」换成顶点各自的可选集，问题随之回到一般着色乃至 list coloring 的范畴，区间图的免费午餐不再成立。此时 §3 的教训仍然值钱：顺序启发式的好坏要靠对照实验判断，不能只凭直觉。
同样的「区间」不只出现在日程表里。一个变量从定义到最后一次使用之间是一段活跃期 (live range)，直线代码里活跃期就是区间、寄存器就是房间——寄存器分配把这套贪心搬进编译器，并处理活跃期被分支搅碎之后的兜底。