座位预约管理系统-LeetCode

1845. 座位预约管理系统

🎯 问题描述（来源于LeetCode）

描述：
请你设计一个管理 n 个座位预约的系统，座位编号从 1 到 n。
请实现 SeatManager 类：

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

说明：

• 每次预约时，必须返回当前所有可预约座位中编号最小的那个。

• 当座位被释放（unreserve）后，它应该重新变为可预约状态，并参与下一次的最小编号比较。

• 示例：

  • 示例 1：

    输入：
    ["SeatManager", "reserve", "reserve", "unreserve", "reserve", "reserve"]
    [[5], [], [], [2], [], []]
    输出：[null, 1, 2, null, 2, 3]
    解释：
    SeatManager seatManager = new SeatManager(5); // 初始化5个座位 [1,2,3,4,5]
    seatManager.reserve();    // 所有座位可预约，返回最小编号 1
    seatManager.reserve();    // 可预约座位为 [2,3,4,5]，返回 2
    seatManager.unreserve(2); // 将座位 2 释放，可预约座位变为 [2,3,4,5]
    seatManager.reserve();    // 返回最小编号 2
    seatManager.reserve();    // 可预约座位为 [3,4,5]，返回 3

💻 解题思路

思路1：最小堆（优先队列）

代码实现

import heapq

class SeatManager:
    def __init__(self, n: int):
        # 初始化包含1到n所有座位编号的最小堆
        self.heap = list(range(1, n + 1))
        heapq.heapify(self.heap)

    def reserve(self) -> int:
        # 弹出并返回当前最小的可预约座位编号
        return heapq.heappop(self.heap)

    def unreserve(self, seatNumber: int) -> None:
        # 将释放的座位编号重新推入堆中，等待下次预约
        heapq.heappush(self.heap, seatNumber)

📊 性能分析

• 时间复杂度：初始化 $O(n)$；reserve 和 unreserve 操作均为 $O(\log n)$。
• 空间复杂度：$O(n)$。需要大小为 $n$ 的堆来存储座位编号。

💡 思考

这道题的核心在于动态维护一个有序集合，并频繁地取出最小值和插入新值。

1. 使用**最小堆（优先队列）**是最完美的解决方案。堆顶永远存放着当前最小的可预约座位编号。
2. 预约时，直接从堆顶弹出（heappop）；释放时，将座位编号重新推入堆中（heappush），堆会自动调整顺序。
3. 相比于使用数组或链表每次遍历查找最小值（$O(n)$），堆的操作效率（$O(\log n)$）要高得多。