Amazon Meeting Rooms III：延后会议后，哪个房间最忙？

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 训练有r个房间0..r-1，空房选最小号，全忙则选最早空闲（tie最小号）；会议延后保留原时长。
• 按原始start顺序调度；原始start互不相同。最多会议计数房间tie最小号，空会议训练返回0。

解题路线

1. free最小堆存可用房号，busy最小堆存(actual_end,room)。每会议先把所有结束≤原start的房间转入free，不能仅释放一个。
2. 有free选最小号按原end结束；无free取最早busy，用ready+(end-start)生成actual_end。不能把会议end直接当延后后的结束。
3. 原始start排序实现等待优先级：更早原start的会议先占下一可用房间。busy heap tie房号对应标准训练规则，两个选择标准由两个堆分工。
4. 计数每次分配+1，最后选(count,-room)最大；最多会议不等于最多忙碌时长，产品指标不同必须改目标。
5. 若原始start重复，需额外规则稳定排序或优先级。题目未公开，本代码拒绝而不替候选人捏造原题tie。

手动走一遍

训练2房，会议[[0,10],[1,5],[2,7],[3,4]]：房0接0..10，房1接1..5与延后5..10，最后房0接10..11；两房均2次，答案0。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

from heapq import heapify,heappop,heappush


def most_used_room(room_count,meetings):
    """Standard training Meeting Rooms III: unique original starts, half-open times."""
    if room_count <= 0 or any(s >= e for s,e in meetings):
        raise ValueError("invalid rooms or durations")
    if len({s for s,e in meetings}) != len(meetings):
        raise ValueError("unique original starts required")
    free=list(range(room_count))
    heapify(free)
    busy=[]
    counts=[0]*room_count
    for start,end in sorted(meetings):
        while busy and busy[0][0] <= start:
            _,room=heappop(busy)
            heappush(free,room)
        if free:
            room=heappop(free)
            actual_end=end
        else:
            ready,room=heappop(busy)
            actual_end=ready+(end-start)
        counts[room]+=1
        heappush(busy,(actual_end,room))
    return max(range(room_count),key=lambda r:(counts[r],-r))

复杂度

n会议、r房，O(n log n+n log(r+1))时间、O(n+r)示例空间；排序输入的流式调度只需O(r)状态。

易错点与追问

容易失分的边界

• 延后后end不加等待时间。
• 仅释放一个到期房导致选错房号。
• 返回累计占用最长房而非最多会议房。

继续深挖

• 同start如何设计优先级？
• 取消会议为何双堆需要版本标记？
• 输入already sorted可否流式？