# 区间分组 给定 $n$ 个区间 $I_1,I_2,\dots,I_n$，其中 $I_i=[l_i,r_i].$ 定义两个区间 $I_i, I_j$ **冲突**当且仅当它们在数轴上有交集，定义如下： - 若 $I_i\cap I_j\neq \varnothing$，则 $I_i$ 与 $I_j$ 冲突； - 等价地，若 $l_i\le r_j$ 且 $l_j\le r_i$，则冲突； 因而同一组内允许的条件是“严格不相交” ： $r_i<l_j \quad \text{或}\quad r_j<l_i.$ 你需要把所有区间分配到若干个“组/颜色”中，使得： 1. 同一组（同一颜色）中的任意两个区间都**不冲突**（即两两严格不相交）； 2. 使用的组数（颜色数） $k$ **尽可能小**； 3. 输出一个长度为 $n$ 的数组 $c_1,c_2,\dots,c_n$，其中 $c_i\in{1,2,\dots,k}$ 表示区间 $I_i$ 被分到的组（颜色）的编号。 ## 贪心策略 1. 将区间按左端点 $l_i$ 升序排序（保留原编号用于答案输出）。 2. 维护一个小根堆，堆元素为 $(\text{该组当前最后区间的右端点}r, \text{组编号 id})$，堆顶是“最早空出来”即 $r$ 最小的组。 3. 依次处理排序后的区间 $[l_i,r_i]$： - 若堆顶满足 $r_{\min}<l_i$，则复用该组：弹出堆顶，把当前区间分配给该组，再把 $(r_i, \text{组编号 id})$ 压回堆； - 否则新开一组：组数更新 $k\leftarrow k+1$，把当前区间分配给第 $k + 1$ 组，并压入 $(r_i,k)$。 4. 输出 $k$ 和每个区间的资源编号（按原顺序）。 ## 最优性证明 #上下界证明法 定义最大重叠数为 $ \omega=\max_t \left|{1 \le i \le n \mid l_i\le t\le r_i}\right|. $ 定义最优答案与贪心得到的组数分别为 $ans,m$。 ### 1) 可行性 算法只在组内当前最右区间的右端点 $R_j<l_i$ 时才把区间 $i$ 放入第 $j$ 组，因此同一组内任意相邻两段满足 $r_{\text{前}}<l_{\text{后}}$，从而组内两两严格不相交，分配合法。 ### 2) 上界：$ans \le m$ 贪心构造出一个使用 $m$ 组的合法分组方案，因此最少组数不可能超过它，因此 $ ans \le m. $ ### 3) 下界：$ans \ge m$ 取达到最大重叠数的时刻 $t^*$。此时有 $\omega$ 个区间满足 $l_i \le t^* \le r_i$，它们两两都在 $t^*$ 处相交，因此任意两个不能放入同一组，故 $ ans \ge \omega. $ 另一方面，贪心最终使用 $m$ 个组，说明在某一步处理区间 $i$ 时不得不开出第 $m$ 组。此时已有 $m - 1$ 个组都无法复用，即对每个组 $1 \le j \le m - 1$ 都有 $R_j \ge l_i$。由于区间按左端点升序处理，每个组中的“最右区间”都满足其左端点 $\le l_i$，于是这 $m - 1$ 个区间都覆盖时刻 $l_i$；再加上当前区间 $i$ 也覆盖 $l_i$，可知在时刻 $l_i$ 时前 $i$ 个区间的重叠数恰为 $m$，而 $\omega$ 是所有区间在任意时刻重叠数的最大值，从而 $ \omega \ge m. $ 因此 $ ans \ge \omega \ge m. $ ### 4) 合并上下界 由 $ans \le m$ 与 $ans \ge m$，推出 $ ans=m. $ 因此贪心策略使用的组数是最小的。 ## 补充：为什么“可复用时选堆顶（最早结束）” 这一步主要是为了高效实现：堆顶最早结束，若它都不能复用（$r_{\min}\not<l$），其它组更不可能复用；若能复用，取它即可。 最优性本身不依赖“选哪一个可复用组”，只要有空的组就复用都不会增加组数，进一步的说明如下。 在处理第 $i$ 个区间的时刻 $l_i$，集合 $ A_i= \{ j \lt i \mid r_j\ge l_i \}. $ 表示覆盖时刻 $l_i$ 的区间（因为 $j \lt i$ 所以 $l_j \le l_i$）。集合的大小 $|A_i|$ 只由输入区间决定，与之前复用了哪个组无关。此刻分组数必为 $|A_i|$，因此： - 若 $|A_i| \lt k$，一定存在空组，复用哪一组都不会改变“是否需要开新组”； - 若 $|A_i| = k$，一定没有空组，任何策略都必须开新组。 所以最终组数完全由这些“被迫开新组”的时刻决定，其恒等于 $\omega$；复用时在所有可复用组中任选一个都不会影响最优性。