What is the main pattern in The Number of the Smallest Unoccupied Chair?

The core pattern is sorting arrivals, then combining timeline scanning with two min-heaps: one for occupied chairs by leaving time and one for reusable chair numbers. That structure enforces both immediate chair reuse and smallest-chair assignment.

Why is a plain array scan not enough for this problem?

A plain scan can find a free chair, but doing that for every arrival can degrade badly as n grows. This problem specifically needs the smallest free chair many times, so a min-heap gives that choice in logarithmic time.

Why do we free chairs before assigning the current arrival?

The statement says a chair becomes free at the exact leaving moment, so an arrival at that same time may use it immediately. If you assign first and release later, you can return a larger chair number than the correct answer.

Can I stop as soon as targetFriend is seated?

Yes. Once you process arrivals in sorted order and correctly release all eligible chairs first, the chair you assign to targetFriend is final, so you can return it immediately.

What data should the occupied heap store?

Store at least leaving time and chair number. The leaving time tells you when the chair becomes reusable, and the chair number is what you push back into the available-chair heap after that friend leaves.

#1942

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

最小未被占据椅子的编号

有 n 个朋友在举办一个派对，这些朋友从 0 到 n - 1 编号。派对里有无数张椅子，编号为 0 到 infinity 。当一个朋友到达派对时，他会占据编号最小且未被占据的椅子。比方说，当一个朋友到达时，如果椅子 0 ， 1 和 5 被占据了，那么他会占据 2 号椅子。当一个朋友离开派…

数组哈希表堆（优先队列）

题目描述

有 n 个朋友在举办一个派对，这些朋友从 0 到 n - 1 编号。派对里有无数张椅子，编号为 0 到 infinity 。当一个朋友到达派对时，他会占据 编号最小 且未被占据的椅子。

比方说，当一个朋友到达时，如果椅子 0 ，1 和 5 被占据了，那么他会占据 2 号椅子。

当一个朋友离开派对时，他的椅子会立刻变成未占据状态。如果同一时刻有另一个朋友到达，可以立即占据这张椅子。

给你一个下标从 0 开始的二维整数数组 times ，其中 times[i] = [arrival_i, leaving_i] 表示第 i 个朋友到达和离开的时刻，同时给你一个整数 targetFriend 。所有到达时间 互不相同 。

请你返回编号为 targetFriend 的朋友占据的 椅子编号 。

示例 1：

输入：times = [[1,4],[2,3],[4,6]], targetFriend = 1
输出：1
解释：
- 朋友 0 时刻 1 到达，占据椅子 0 。
- 朋友 1 时刻 2 到达，占据椅子 1 。
- 朋友 1 时刻 3 离开，椅子 1 变成未占据。
- 朋友 0 时刻 4 离开，椅子 0 变成未占据。
- 朋友 2 时刻 4 到达，占据椅子 0 。
朋友 1 占据椅子 1 ，所以返回 1 。

示例 2：

输入：times = [[3,10],[1,5],[2,6]], targetFriend = 0
输出：2
解释：
- 朋友 1 时刻 1 到达，占据椅子 0 。
- 朋友 2 时刻 2 到达，占据椅子 1 。
- 朋友 0 时刻 3 到达，占据椅子 2 。
- 朋友 1 时刻 5 离开，椅子 0 变成未占据。
- 朋友 2 时刻 6 离开，椅子 1 变成未占据。
- 朋友 0 时刻 10 离开，椅子 2 变成未占据。
朋友 0 占据椅子 2 ，所以返回 2 。

提示：

n == times.length
2 <= n <= 10⁴
times[i].length == 2
1 <= arrival_i < leaving_i <= 10⁵
0 <= targetFriend <= n - 1
每个 arrival_i 时刻 互不相同 。

lightbulb

解题思路

方法一：优先队列（小根堆）

我们首先将每个朋友的到达时间、离开时间和编号组成一个三元组，然后按到达时间排序。

我们使用一个小根堆 $\textit{idle}$ 来存储当前空闲的椅子编号，初始时，我们将 $0, 1, \ldots, n-1$ 加入 $\textit{idle}$ 中。使用一个小根堆 $\textit{busy}$ 存储二元组 $(\textit{leaving}, \textit{chair})$ ，其中 $\textit{leaving}$ 表示离开时间，而 $\textit{chair}$ 表示椅子编号。

遍历每个朋友的到达时间、离开时间和编号，对于每个朋友，我们首先将所有离开时间小于等于当前朋友到达时间的朋友从 $\textit{busy}$ 中弹出，将他们占据的椅子编号加入 $\textit{idle}$ 中。然后我们从 $\textit{idle}$ 中弹出一个椅子编号，将其分配给当前朋友，将 $(\textit{leaving}, \textit{chair})$ 加入 $\textit{busy}$ 中。如果当前朋友的编号等于 $\textit{targetFriend}$ ，我们返回当前分配的椅子编号。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为朋友的个数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

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))

speed

复杂度分析

指标	值
时间	O(n \log n)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
They point out that arrivals are distinct and suggest sorting by arrival time first.
question_mark
They ask what should happen when someone leaves at the exact time another friend arrives.
question_mark
They want the smallest available chair quickly, which is a strong hint for a min-heap instead of linear scanning.

warning

常见陷阱

外企场景

error
Freeing only one departed chair before seating the next friend instead of all chairs with leaving time less than or equal to the current arrival.
error
Using a hash table or array scan alone for chair selection, which misses the need to get the globally smallest free chair efficiently.
error
Losing the original friend index after sorting and returning the chair for the wrong person instead of targetFriend.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return the full chair assignment array for every friend instead of only the target friend's chair.
arrow_right_alt
Process online arrivals and departures where events are streamed rather than given as a full array upfront.
arrow_right_alt
Replace smallest-chair assignment with another seating rule, such as largest free chair or nearest reusable chair.

help

常见问题

外企场景

继续练习

#1912 设计电影租借系统 #2099 找到和最大的长度为 K 的子序列 #2342 数位和相等数对的最大和