题目描述
思路解析动画文字版
记牢这套调度:先归还已经离场的椅子,再分配编号最小的空椅。下面把两个堆画成一排椅子加一张忙碌表,一步步走给你看。
开场 · 5 把椅子全空：一排椅子编号 0 到 4,开场全是空的。5 位朋友已经按到达时刻从早到晚排好队。右侧这张忙碌堆现在是空的,它专门记录正在座位上、还没离场的人,并且按离场时刻从早到晚排,堆顶那行就是最快要走的一位。
两件法宝 · 空椅取最小,忙碌堆按离场：整套算法就靠两件法宝。第一件:每次分座,取所有空椅里编号最小的那把,画面上就是最左边那把空椅。第二件:每来一位朋友之前,先看忙碌堆堆顶,谁的离场时刻已经不晚于当前时刻,就让他离席、把椅子还回来。理解了这两件事,后面每一帧都在反复用它们。
朋友 0 到达 t=1：朋友 0 在时刻 1 到达。先按规矩看一眼忙碌堆,现在它是空的,没有人需要离席,直接进入分座。
取最小空椅 → 椅 0：现在的空椅有 0、1、2、3、4,其中编号最小的是椅 0,它就是空椅小根堆的堆顶。把它点亮成紫色,准备分给朋友 0。开场大家都空着,自然从椅 0 开坐。
朋友 0 落座 椅 0 · 记入忙碌堆：朋友 0 坐下椅 0,这把椅子变蓝表示占用。同时把他的离场时刻 5 和椅号 0 打包压进忙碌堆,右侧面板新增一行并高亮。忙碌堆始终按离场时刻排序,方便下次一眼看到谁最先走。
朋友 1 到达 t=2：朋友 1 在时刻 2 到达。看忙碌堆堆顶,最快离场的也要到时刻 5,比现在的 2 还晚,所以此刻没有人离席,直接分座。
取最小空椅 → 椅 1：现在的空椅有 1、2、3、4,其中编号最小的是椅 1,它就是空椅小根堆的堆顶。把它点亮成紫色,准备分给朋友 1。
朋友 1 落座 椅 1 · 记入忙碌堆：朋友 1 坐下椅 1,这把椅子变蓝表示占用。同时把他的离场时刻 4 和椅号 1 打包压进忙碌堆,右侧面板新增一行并高亮。忙碌堆始终按离场时刻排序,方便下次一眼看到谁最先走。
朋友 2 到达 t=3：朋友 2 在时刻 3 到达。看忙碌堆堆顶,最快离场的也要到时刻 4,比现在的 3 还晚,所以此刻没有人离席,直接分座。
取最小空椅 → 椅 2：现在的空椅有 2、3、4,其中编号最小的是椅 2,它就是空椅小根堆的堆顶。把它点亮成紫色,准备分给朋友 2。
朋友 2 落座 椅 2 · 记入忙碌堆：朋友 2 坐下椅 2,这把椅子变蓝表示占用。同时把他的离场时刻 10 和椅号 2 打包压进忙碌堆,右侧面板新增一行并高亮。忙碌堆始终按离场时刻排序,方便下次一眼看到谁最先走。
朋友 3 到达 t=6：朋友 3 在时刻 6 到达。看忙碌堆堆顶,离场时刻 4 已经不晚于 6,说明有人在他到之前就走了。接下来用一个循环,把所有离场时刻小于等于 6 的人挨个请离席、椅子还回去。
释放 · 朋友 1 离席,椅 1 收回：忙碌堆堆顶原本是朋友 1,离场时刻 4,不晚于当前的 6。把他从堆里弹出,右侧忙碌表这一行随之消失;他坐的椅 1 立刻变空、还回空椅集合,画面上这把椅子闪成绿色。弹完继续看新的堆顶,直到堆顶离场时刻超过当前时刻为止。
释放 · 朋友 0 离席,椅 0 收回：忙碌堆堆顶原本是朋友 0,离场时刻 5,不晚于当前的 6。把他从堆里弹出,右侧忙碌表这一行随之消失;他坐的椅 0 立刻变空、还回空椅集合,画面上这把椅子闪成绿色。弹完继续看新的堆顶,直到堆顶离场时刻超过当前时刻为止。
释放到此为止 · 堆顶离场 10 大于 6：再看堆顶,现在最快离场的要到时刻 10,已经晚于当前的 6,说明剩下的人都还没走。释放循环就此打住,回收阶段结束,接下来给朋友 3 分座。
取最小空椅 → 椅 0：现在的空椅有 0、1、3、4,其中编号最小的是椅 0,它就是空椅小根堆的堆顶。把它点亮成紫色,准备分给朋友 3。
朋友 3 落座 椅 0 · 记入忙碌堆：朋友 3 坐下椅 0,这把椅子变蓝表示占用。同时把他的离场时刻 8 和椅号 0 打包压进忙碌堆,右侧面板新增一行并高亮。忙碌堆始终按离场时刻排序,方便下次一眼看到谁最先走。
朋友 4 到达 t=7 · 目标朋友：朋友 4 在时刻 7 到达。看忙碌堆堆顶,最快离场的也要到时刻 8,比现在的 7 还晚,所以此刻没有人离席,直接分座。 注意,这位就是我们要盯的目标朋友。
取最小空椅 → 椅 1：现在的空椅有 1、3、4,其中编号最小的是椅 1,它就是空椅小根堆的堆顶。把它点亮成紫色,准备分给朋友 4。
目标朋友 4 落座 椅 1 → 答案：朋友 4 正是目标朋友,他坐下了椅 1。算法到这里就可以直接收工,把 1 返回,这就是答案。回头看,椅 1 原本是朋友 1 坐过、时刻 4 空出来的,一路留到了现在被目标朋友接手。
回放 · 目标朋友坐椅 1,答案 1：把全程串一遍。前面几位依次坐下椅 0、椅 1、椅 2;朋友 1 时刻 4 离场腾出椅 1;朋友 3 时刻 6 到达时,椅 0 和椅 1 都空,他挑了编号更小的椅 0;于是椅 1 一直空着,等到目标朋友 4 时刻 7 进场,顺理成章坐上椅 1。答案就是 1。整套流程始终只做两件事:先归还离场的椅子,再取最小编号的空椅。
边界想清:最先到达者坐椅 0、离场时刻等于到达时刻要先释放、椅子可以链式复用回椅 0。
面试重点:两个小根堆分别取最小空椅与最快离场、只按到达排序、复杂度 O(n log n)。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def smallestChair(self, times: List[List[int]], targetFriend: int) -> int: n = len(times) for i in range(n): times[i].append(i) times.sort() idle = list(range(n)) heapify(idle) busy = [] for arrival, leaving, i in times: while busy and busy[0][0] <= arrival: heappush(idle, heappop(busy)[1]) j = heappop(idle) if i == targetFriend: return j heappush(busy, (leaving, j))复杂度
- 时间：O(n log n)，n 位朋友。排序是 O(n log n);之后每位朋友最多向两个堆各做常数次弹出与插入,每次堆操作 O(log n),累计也是 O(n log n)。整体由排序和堆操作共同决定,是 O(n log n)
- 空间：O(n)，按峰值算。两个小根堆里的元素加起来最多就是 n 个(每位朋友要么在座、要么椅子空着)。排序的额外开销分语言:C 加加与 Java 通常是 O(log n) 递归栈,Python 的 Timsort 最坏 O(n)。总体空间是 O(n)
易错点
面试追问把动画讲成自己的话
追问这题的核心思路是什么?
追问能不能不用堆?
追问为什么只按到达排序、不单独排离场事件也对?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
移除石子使总数最小
LeetCode 1962 · 中等 · 沿着 堆套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题