酒店客房分配优化：求接待最多客人的客房及客人数

问题概述 #

酒店拥有编号1到n的n间客房，m位客人的预订请求格式为[到达时间, 时长]。分配规则为：客人到达时，优先分配编号最小的空闲客房；无空闲客房则忽略该请求。最终需找出接待客人最多的客房编号列表及对应客人数。

示例：
客人请求：[[10, 2], [10,3], [12, 2], [9,3], [11,2], [13,4]]
客房总数=6
分配结果：

• 1号房：接待2位客人（[9,3]、[12,2]）
• 2号房：接待2位客人（[10,2]、[13,4]）
• 3-4号房各接待1位客人
  最终返回客房列表[1,2]，客人数2。

现有解法及瓶颈 #

当前解法步骤：

1. 按客人到达时间排序所有请求，时间复杂度O(m log m)；
2. 逐个遍历客人，检查每间客房是否空闲（客房结束时间≤客人到达时间），找到编号最小的空闲客房分配，时间复杂度O(m*n)；
3. 统计各客房接待次数，得出结果。

整体复杂度为O(m log m + m*n)，当n或m规模较大时，遍历所有客房的操作会成为性能瓶颈。

优化方案：基于优先队列的高效分配 #

通过引入两个优先队列（最小堆），可以将时间复杂度优化至O(m log m + m log n)，核心思路是减少空闲客房的查找开销：

核心数据结构 #

• 空闲客房堆：最小堆，存储空闲客房编号，可O(log n)时间取出编号最小的空闲客房；
• 占用客房堆：最小堆，存储被占用客房的[结束时间, 客房编号]，按结束时间升序排序（结束时间相同时按客房编号升序），可O(log n)时间找到最早空闲的客房。

具体实现步骤 #

1. 预处理请求：将所有客人的[到达时间, 时长]转换为[到达时间, 结束时间]（结束时间=到达时间+时长），然后按到达时间升序排序，耗时O(m log m)；
2. 初始化堆：
   • 空闲客房堆：将1到n的客房编号全部加入最小堆；
   • 占用客房堆：初始为空；
3. 处理每个客人请求：
   • 先清理占用堆：将所有结束时间≤当前客人到达时间的客房从占用堆中取出，放回空闲客房堆；
   • 若空闲堆不为空：
     • 取出堆顶的最小编号客房；
     • 将该客房的[客人结束时间, 客房编号]加入占用堆；
     • 对应客房的接待次数加1；
   • 若空闲堆为空，直接忽略该客人；
4. 统计结果：遍历所有客房的接待次数，找出最大值，收集所有达到该次数的客房编号。

复杂度分析 #

• 排序请求：O(m log m)；
• 堆操作：每个客人处理时的堆操作（取出、插入）均为O(log n)，每个客房最多被放入和取出占用堆各一次，总堆操作耗时O(m log n)；
• 统计结果：O(n)；
  整体复杂度优化为O(m log m + m log n)，在大样本场景下性能远优于原解法。

示例验证（n=6） #

1. 转换并排序后的客人请求：[[9,12], [10,12], [10,13], [11,13], [12,14], [13,17]]；
2. 初始空闲堆：[1,2,3,4,5,6]；
3. 处理[9,12]：取1号房，加入占用堆[(12,1)]，1号房次数=1；
4. 处理[10,12]：取2号房，加入占用堆[(12,1), (12,2)]，2号房次数=1；
5. 处理[10,13]：取3号房，加入占用堆[(12,1), (12,2), (13,3)]，3号房次数=1；
6. 处理[11,13]：取4号房，加入占用堆[(12,1), (12,2), (13,3), (13,4)]，4号房次数=1；
7. 处理[12,14]：清理占用堆，将(12,1)、(12,2)放回空闲堆，取1号房加入占用堆[(13,3), (13,4), (14,1)]，1号房次数=2；
8. 处理[13,17]：清理占用堆，将(13,3)、(13,4)放回空闲堆，取2号房加入占用堆[(14,1), (17,2)]，2号房次数=2；
9. 统计得1、2号房接待次数最多，符合示例结果。

内容的提问来源于stack exchange，提问作者Mayank Sinha