题目描述
思路解析动画文字版
记住这句:每场会议先「把到点的房从 busy 退回 free」,再「有空房用编号最小、没空房延后到最早空出」。下面每一帧都在套它。
开局所有房都空闲,free 小根堆里是编号 0、1、2,堆顶 0 是最小编号。busy 堆(右侧面板)是空的,还没有房在用。
第 1 场会议来了,区间 [1, 20),时长 19。先看有没有房到点该退回空闲:把 busy 堆里结束时间 ≤ 1 的房弹回 free。
此时 busy 堆是空的,没有正在用的房,直接进入分配。
free 里有空房,弹堆顶房0(编号最小)给这场会议。它正常占用到本场 end=20。房0 使用次数加到 1。把「20@房0」塞进 busy 堆。
第 1 场落定:房0 用到 20(写进 busy 堆,右侧面板按结束时间重新冒泡)。现在 free=[1, 2]、busy 有 1 间房在用。继续下一场。
第 2 场会议来了,区间 [2, 10),时长 8。先看有没有房到点该退回空闲:把 busy 堆里结束时间 ≤ 2 的房弹回 free。
检查 busy 堆顶:最早空出的房要到 20 才结束,而本场 2 就开始,20 还没到,所以这一步没有房可退回。
free 里有空房,弹堆顶房1(编号最小)给这场会议。它正常占用到本场 end=10。房1 使用次数加到 1。把「10@房1」塞进 busy 堆。
第 2 场落定:房1 用到 10(写进 busy 堆,右侧面板按结束时间重新冒泡)。现在 free=[2]、busy 有 2 间房在用。继续下一场。
第 3 场会议来了,区间 [3, 5),时长 2。先看有没有房到点该退回空闲:把 busy 堆里结束时间 ≤ 3 的房弹回 free。
检查 busy 堆顶:最早空出的房要到 10 才结束,而本场 3 就开始,10 还没到,所以这一步没有房可退回。
free 里有空房,弹堆顶房2(编号最小)给这场会议。它正常占用到本场 end=5。房2 使用次数加到 1。把「5@房2」塞进 busy 堆。
第 3 场落定:房2 用到 5(写进 busy 堆,右侧面板按结束时间重新冒泡)。现在 free=[空]、busy 有 3 间房在用。继续下一场。
第 4 场会议来了,区间 [4, 9),时长 5。先看有没有房到点该退回空闲:把 busy 堆里结束时间 ≤ 4 的房弹回 free。
检查 busy 堆顶:最早空出的房要到 5 才结束,而本场 4 就开始,5 还没到,所以这一步没有房可退回。
free 空了,没有现成空房,本场要延后。弹 busy 堆顶房2(最早在 5 空出),它一空就接着开这场,新结束 = 原结束 5 + 时长 5 = 10。房2 使用次数加到 2。
第 4 场落定:房2 用到 10(写进 busy 堆,右侧面板按结束时间重新冒泡)。现在 free=[空]、busy 有 3 间房在用。继续下一场。
第 5 场会议来了,区间 [6, 8),时长 2。先看有没有房到点该退回空闲:把 busy 堆里结束时间 ≤ 6 的房弹回 free。
检查 busy 堆顶:最早空出的房要到 10 才结束,而本场 6 就开始,10 还没到,所以这一步没有房可退回。
free 空了,没有现成空房,本场要延后。弹 busy 堆顶房1(最早在 10 空出),它一空就接着开这场,新结束 = 原结束 10 + 时长 2 = 12。房1 使用次数加到 2。
第 5 场落定:房1 用到 12(写进 busy 堆,右侧面板按结束时间重新冒泡)。现在 free=[空]、busy 有 3 间房在用。所有会议处理完毕。
五场会议处理完,使用次数是 房0:1、房1:2、房2:2。房1 和房2 都用了 2 次并列最多,按规则取编号小的,所以答案是房 1。靠「free 按编号、busy 按结束时间」两个堆,每步都能 O(log n) 拿到最小编号空房或最早空出的房。
边界:n=1 都用房 0,重叠才延后、已结束则先释放再分配,答案恒为 0;互不冲突时每次从 free 取最小编号、可能反复用同一低编号房;同时空出取编号小。
面试常问:双堆把 O(n) 查找降到 O(log n);busy 元素存「结束, 房号」用于计数与平局。
参考代码
from typing import Listimport heapqclass Solution: def mostBooked(self, n: int, meetings: List[List[int]]) -> int: meetings.sort() free = list(range(n)) heapq.heapify(free) busy = [] count = [0] * n for start, end in meetings: while busy and busy[0][0] <= start: _, room = heapq.heappop(busy) heapq.heappush(free, room) duration = end - start if free: room = heapq.heappop(free) finish = end else: t, room = heapq.heappop(busy) finish = t + duration count[room] += 1 heapq.heappush(busy, (finish, room)) return max(range(n), key=lambda i: (count[i], -i))复杂度
- 时间：O(m log m + m log n)，m 场会议先排序 O(m log m);每场常数次堆操作,每次 O(log n)(两个堆各最多 n 个元素),共 m 场
- 空间：O(n)，free 堆与 busy 堆里的房号总数不超过 n,外加 count 数组 O(n)
易错点
面试追问把动画讲成自己的话
追问为什么用两个堆,而不是每次扫一遍 n 间房找空房或最早空出的房?
追问busy 堆里为什么要把房号也存进去,只存结束时间不行吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。再去主线里挑下一道练手。
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题