LeetCode 1942中等堆 · 优先队列
最小未被占据椅子的编号 图解题解
这道题到底在问什么
有 n 位朋友编号 0 到 n 减 1,椅子编号 0 到无穷。朋友到达时占据编号最小的空椅,离场时椅子立即变空。times[i] = [到达, 离场],所有到达时刻互不相同。返回编号为 targetFriend 的朋友所占据的椅子编号。
- 输入
- times=[[1,5],[2,4],[3,10],[6,8],[7,9]], targetFriend=4
- 输出
- 1
- 输入
- times=[[1,4],[2,3],[4,6]], targetFriend=1
- 输出
- 1
先想最直接的笨办法
朋友 3 在时刻 6 到达。看忙碌堆堆顶,离场时刻 4 已经不晚于 6,说明有人在他到之前就走了。接下来用一个循环,把所有离场时刻小于等于 6 的人挨个请离席、椅子还回去。（动画第 15 步）
最优解：一步一步想明白
- 3记牢这套调度:先归还已经离场的椅子,再分配编号最小的空椅。下面把两个堆画成一排椅子加一张忙碌表,一步步走给你看。
- 4一排椅子编号 0 到 4,开场全是空的。5 位朋友已经按到达时刻从早到晚排好队。右侧这张忙碌堆现在是空的,它专门记录正在座位上、还没离场的人,并且按离场时刻从早到晚排,堆顶那行就是最快要走的一位。
- 5整套算法就靠两件法宝。第一件:每次分座,取所有空椅里编号最小的那把,画面上就是最左边那把空椅。第二件:每来一位朋友之前,先看忙碌堆堆顶,谁的离场时刻已经不晚于当前时刻,就让他离席、把椅子还回来。理解了这两件事,后面每一帧都在反复用它们。
- 6朋友 0 在时刻 1 到达。先按规矩看一眼忙碌堆,现在它是空的,没有人需要离席,直接进入分座。
- 7现在的空椅有 0、1、2、3、4,其中编号最小的是椅 0,它就是空椅小根堆的堆顶。把它点亮成紫色,准备分给朋友 0。开场大家都空着,自然从椅 0 开坐。
- 8朋友 0 坐下椅 0,这把椅子变蓝表示占用。同时把他的离场时刻 5 和椅号 0 打包压进忙碌堆,右侧面板新增一行并高亮。忙碌堆始终按离场时刻排序,方便下次一眼看到谁最先走。
- 9朋友 1 在时刻 2 到达。看忙碌堆堆顶,最快离场的也要到时刻 5,比现在的 2 还晚,所以此刻没有人离席,直接分座。
- 10现在的空椅有 1、2、3、4,其中编号最小的是椅 1,它就是空椅小根堆的堆顶。把它点亮成紫色,准备分给朋友 1。
- 11朋友 1 坐下椅 1,这把椅子变蓝表示占用。同时把他的离场时刻 4 和椅号 1 打包压进忙碌堆,右侧面板新增一行并高亮。忙碌堆始终按离场时刻排序,方便下次一眼看到谁最先走。
- 12朋友 2 在时刻 3 到达。看忙碌堆堆顶,最快离场的也要到时刻 4,比现在的 3 还晚,所以此刻没有人离席,直接分座。
- 13现在的空椅有 2、3、4,其中编号最小的是椅 2,它就是空椅小根堆的堆顶。把它点亮成紫色,准备分给朋友 2。
- 14朋友 2 坐下椅 2,这把椅子变蓝表示占用。同时把他的离场时刻 10 和椅号 2 打包压进忙碌堆,右侧面板新增一行并高亮。忙碌堆始终按离场时刻排序,方便下次一眼看到谁最先走。
- 15朋友 3 在时刻 6 到达。看忙碌堆堆顶,离场时刻 4 已经不晚于 6,说明有人在他到之前就走了。接下来用一个循环,把所有离场时刻小于等于 6 的人挨个请离席、椅子还回去。
- 16忙碌堆堆顶原本是朋友 1,离场时刻 4,不晚于当前的 6。把他从堆里弹出,右侧忙碌表这一行随之消失;他坐的椅 1 立刻变空、还回空椅集合,画面上这把椅子闪成绿色。弹完继续看新的堆顶,直到堆顶离场时刻超过当前时刻为止。
- 17忙碌堆堆顶原本是朋友 0,离场时刻 5,不晚于当前的 6。把他从堆里弹出,右侧忙碌表这一行随之消失;他坐的椅 0 立刻变空、还回空椅集合,画面上这把椅子闪成绿色。弹完继续看新的堆顶,直到堆顶离场时刻超过当前时刻为止。
- 18再看堆顶,现在最快离场的要到时刻 10,已经晚于当前的 6,说明剩下的人都还没走。释放循环就此打住,回收阶段结束,接下来给朋友 3 分座。
- 19现在的空椅有 0、1、3、4,其中编号最小的是椅 0,它就是空椅小根堆的堆顶。把它点亮成紫色,准备分给朋友 3。
- 20朋友 3 坐下椅 0,这把椅子变蓝表示占用。同时把他的离场时刻 8 和椅号 0 打包压进忙碌堆,右侧面板新增一行并高亮。忙碌堆始终按离场时刻排序,方便下次一眼看到谁最先走。
- 21朋友 4 在时刻 7 到达。看忙碌堆堆顶,最快离场的也要到时刻 8,比现在的 7 还晚,所以此刻没有人离席,直接分座。 注意,这位就是我们要盯的目标朋友。
- 22现在的空椅有 1、3、4,其中编号最小的是椅 1,它就是空椅小根堆的堆顶。把它点亮成紫色,准备分给朋友 4。
- 23朋友 4 正是目标朋友,他坐下了椅 1。算法到这里就可以直接收工,把 1 返回,这就是答案。回头看,椅 1 原本是朋友 1 坐过、时刻 4 空出来的,一路留到了现在被目标朋友接手。
- 24把全程串一遍。前面几位依次坐下椅 0、椅 1、椅 2;朋友 1 时刻 4 离场腾出椅 1;朋友 3 时刻 6 到达时,椅 0 和椅 1 都空,他挑了编号更小的椅 0;于是椅 1 一直空着,等到目标朋友 4 时刻 7 进场,顺理成章坐上椅 1。答案就是 1。整套流程始终只做两件事:先归还离场的椅子,再取最小编号的空椅。
⚠️ 容易写错的地方
✗ 错：直接按输入顺序处理朋友
✓ 对：先按到达时刻排序再模拟
座位分配依赖时间先后,不排序就会把后到的人当成先到,分错椅子
✗ 错：每步用线性扫描找最小空椅或最快离场
✓ 对：用两个小根堆各 O(log n) 拿堆顶
朋友数可达一万,线性找最小会让整体退化到 O(n 的平方),数据一大就超时
✗ 错：释放椅子只用一个 if 判一次
✓ 对：用 while 循环把所有到点该走的人全弹出
同一个到达时刻之前,可能已经有好几位的离场时刻都到了,只弹一个会漏掉其余空椅,分座偏大
✗ 错：释放条件写成离场严格小于到达
✓ 对：写成离场小于等于到达
题意规定同一时刻离场的椅子可被同刻到达的人立即占用,离场时刻正好等于到达时刻也要先释放
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from 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 = right
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class 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))C++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
int smallestChair(vector<vector<int>>& times, int targetFriend) {
using pii = pair<int, int>;
priority_queue<pii, vector<pii>, greater<pii>> busy;
priority_queue<int, vector<int>, greater<int>> idle;
int n = times.size();
for (int i = 0; i < n; ++i) {
times[i].push_back(i);
idle.push(i);
}
sort(times.begin(), times.end());
for (const auto& e : times) {
int arrival = e[0], leaving = e[1], i = e[2];
while (!busy.empty() && busy.top().first <= arrival) {
idle.push(busy.top().second);
busy.pop();
}
int j = idle.top();
if (i == targetFriend) {
return j;
}
idle.pop();
busy.emplace(leaving, j);
}
return -1;
}
};Java
import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
public int smallestChair(int[][] times, int targetFriend) {
int n = times.length;
PriorityQueue<Integer> idle = new PriorityQueue<>();
PriorityQueue<int[]> busy = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
for (int i = 0; i < n; ++i) {
times[i] = new int[] {times[i][0], times[i][1], i};
idle.offer(i);
}
Arrays.sort(times, Comparator.comparingInt(a -> a[0]));
for (int[] e : times) {
int arrival = e[0], leaving = e[1], i = e[2];
while (!busy.isEmpty() && busy.peek()[0] <= arrival) {
idle.offer(busy.poll()[1]);
}
int j = idle.poll();
if (i == targetFriend) {
return j;
}
busy.offer(new int[] {leaving, j});
}
return -1;
}
}复杂度
时间
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)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 最小未被占据椅子的编号 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题的核心思路是什么?+
事件模拟加两个小根堆。把朋友按到达时刻排序,逐个处理;维护一个空椅堆按编号取最小、一个忙碌堆按离场时刻取最快离场。每来一位,先把离场时刻不晚于当前时刻的人全部弹出、椅子归还,再取最小编号空椅分给他,命中目标就返回。
能不能不用堆?+
可以用有序集合维护空椅编号、用按离场时刻有序的结构维护在座的人,复杂度同样是 O(n log n)。也有人用事件扫描加计数,但对本题两个小根堆写起来最直接、最好想。核心都是快速拿到最小空椅和最快离场者。
为什么只按到达排序、不单独排离场事件也对?+
因为离场只在有新朋友到达、需要腾椅子时才被关心。到达时刻互不相同,天然有先后;每次到达前用忙碌堆按需弹出所有已离场的人即可,不必把离场也做成独立事件去排序。这样一遍扫描就够,复杂度稳定在 O(n log n)。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 最小未被占据椅子的编号 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。