What is the main pattern behind Seat Reservation Manager?

It combines design with a min-heap priority queue to always retrieve the lowest-numbered available seat efficiently.

Can I use a simple array instead of a heap?

Using an array leads to O(n) reserve operations, which is too slow for large n. A heap maintains O(log n) efficiency.

How do I handle unreserve calls safely?

Push the unreserved seat back into the heap and optionally mark it in a tracking array to prevent duplicates.

What is the time complexity per operation?

Each reserve or unreserve operation runs in O(log n) due to heap insertion and removal.

Can this approach handle the maximum constraints?

Yes, the min-heap approach efficiently manages up to 10^5 seats and 10^5 operations without performance issues.

#1845

Medium

auto_awesome堆

LeetCode 题解工作台

座位预约管理系统

请你设计一个管理 n 个座位预约的系统，座位编号从 1 到 n 。请你实现 SeatManager 类： SeatManager(int n) 初始化一个 SeatManager 对象，它管理从 1 到 n 编号的 n 个座位。所有座位初始都是可预约的。 int reserve() 返回可以预约座…

设计堆（优先队列）

题目描述

请你设计一个管理 n 个座位预约的系统，座位编号从 1 到 n 。

请你实现 SeatManager 类：

SeatManager(int n) 初始化一个 SeatManager 对象，它管理从 1 到 n 编号的 n 个座位。所有座位初始都是可预约的。
int reserve() 返回可以预约座位的 最小编号 ，此座位变为不可预约。
void unreserve(int seatNumber) 将给定编号 seatNumber 对应的座位变成可以预约。

示例 1：

输入：
["SeatManager", "reserve", "reserve", "unreserve", "reserve", "reserve", "reserve", "reserve", "unreserve"]
[[5], [], [], [2], [], [], [], [], [5]]
输出：
[null, 1, 2, null, 2, 3, 4, 5, null]

解释：
SeatManager seatManager = new SeatManager(5); // 初始化 SeatManager ，有 5 个座位。
seatManager.reserve();    // 所有座位都可以预约，所以返回最小编号的座位，也就是 1 。
seatManager.reserve();    // 可以预约的座位为 [2,3,4,5] ，返回最小编号的座位，也就是 2 。
seatManager.unreserve(2); // 将座位 2 变为可以预约，现在可预约的座位为 [2,3,4,5] 。
seatManager.reserve();    // 可以预约的座位为 [2,3,4,5] ，返回最小编号的座位，也就是 2 。
seatManager.reserve();    // 可以预约的座位为 [3,4,5] ，返回最小编号的座位，也就是 3 。
seatManager.reserve();    // 可以预约的座位为 [4,5] ，返回最小编号的座位，也就是 4 。
seatManager.reserve();    // 唯一可以预约的是座位 5 ，所以返回 5 。
seatManager.unreserve(5); // 将座位 5 变为可以预约，现在可预约的座位为 [5] 。

提示：

1 <= n <= 10⁵
1 <= seatNumber <= n
每一次对 reserve 的调用，题目保证至少存在一个可以预约的座位。
每一次对 unreserve 的调用，题目保证 seatNumber 在调用函数前都是被预约状态。
对 reserve 和 unreserve 的调用总共不超过 10⁵ 次。

lightbulb

解题思路

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

我们定义一个优先队列（小根堆） $\textit{q}$ ，用于存储所有可预约的座位编号。初始时，我们将 $1$ 到 $n$ 的所有座位编号加入到 $\textit{q}$ 中。

调用 reserve 方法时，我们从 $\textit{q}$ 中弹出堆顶元素，即可预约的座位编号的最小值。

调用 unreserve 方法时，我们将座位编号加入到 $\textit{q}$ 中。

时间复杂度方面，初始化的时间复杂度为 $O(n)$ 或 $O(n \times \log n)$ ，reserve 和 unreserve 方法的时间复杂度均为 $O(\log n)$ 。空间复杂度为 $O(n)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

class SeatManager:
    def __init__(self, n: int):
        self.q = list(range(1, n + 1))

    def reserve(self) -> int:
        return heappop(self.q)

    def unreserve(self, seatNumber: int) -> None:
        heappush(self.q, seatNumber)


# Your SeatManager object will be instantiated and called as such:
# obj = SeatManager(n)
# param_1 = obj.reserve()
# obj.unreserve(seatNumber)

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
Are you using a data structure that always gives the smallest available seat?
question_mark
Can your design handle up to 10^5 seats efficiently without linear scans?
question_mark
How do you ensure unreserve operations maintain heap consistency?

warning

常见陷阱

外企场景

error
Using a simple array scan for reserve leads to O(n) per operation and times out on large n.
error
Not pushing unreserved seats back into the heap correctly can break the ordering guarantee.
error
Ignoring seat state validation may allow unreserve on an already unreserved seat.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Track multiple classes of seats (premium, regular) using separate heaps.
arrow_right_alt
Implement the same SeatManager but with random seat assignment instead of lowest-numbered.
arrow_right_alt
Extend to support batch reserve or unreserve operations efficiently.

help

常见问题

外企场景

继续练习

#1825 求出 MK 平均值 #1912 设计电影租借系统 #2034 股票价格波动