下面是压缩版证明（本题复用条件是严格的：只有当 $b_{\text{前}}<a_{\text{后}}$ 才能同房，因此把每位顾客视为闭区间 $[a,b]$，端点相等也算冲突）。 --- ## 最大重叠数 = 最小房间数 将第 $i$ 位顾客对应为区间 $I_i=[a_i,b_i]$。定义最大重叠数为 $ \omega=\max_t |\{1 \le i \le n \mid a_i\le t\le b_i\}|. $ ### 1) 下界：任何方案都需要 $\ge \omega$ 间房 取一个使重叠达到最大值的时刻 $t^*$。此时有 $\omega$ 位顾客同时在住，同一时刻每个房间最多住 $1$ 人，因此任意方案的房间数 $k$ 满足 $k\ge \omega$。 ### 2) 上界：贪心方案所用房间数 $\le \omega$ 将顾客按到达日 $a$ 升序处理。处理到顾客 $i$（到达日为 $a_i$）时，已处理顾客中仍在住的集合为 $ A_i= \{ 1 \le j<i\mid b_j\ge a_i \}. $ 由于已排序，$j<i$ 保证 $a_j\le a_i$，因此 $j\in A_i$ 等价于区间 $[a_j,b_j]$ 覆盖时刻 $a_i$，即此刻 $j$ 仍占用一个房间，所以此刻占用房间数恰为 $|A_i|$，而 $|A_i|$ 是前 $i - 1$ 个区间在时刻 $a_i$ 的重叠数。 - 若 $|A_i|<k$（$k$ 为已开的房间数），则存在空房可复用，不会开新房； - 若 $|A_i|=k$，则无空房，只能开新房。开后房间数变为 $k+1$，且此刻同时在住人数为 $|A_i|+1=k+1$，$k + 1$ 为前 $i$ 个区间在时刻 $a_i$ 的重叠数，而 $\omega$ 是全体区间的最大重叠数，因此 $\omega\ge k+1$。 所以房间数在整个过程中最多增长到 $\omega$，贪心的最终答案 $k_{\text{alg}}$ 满足 $k_{\text{alg}}\le \omega$。 结合下界 $k\ge \omega$，得到 $k_{\text{alg}}=\omega$，算法最优。 --- ## 多个房间可复用时，任选一个也保证最优 在处理第 $i$ 位顾客的时刻 $a_i$，集合 $ A_i= \{ j<i\mid b_j\ge a_i \}. $ 的大小 $|A_i|$ 只由输入区间决定，与之前复用了哪间房无关。此刻占用房间数必为 $|A_i|$，因此： - 若 $|A_i|<k$，一定存在空房，复用哪一间都不会改变“是否需要开新房”； - 若 $|A_i|=k$，一定没有空房，任何策略都必须开新房。 所以最终房间数完全由这些“被迫开新房”的时刻决定，恒等于 $\omega$；复用时在所有可复用房间中任选一个都不会影响最优性。