Medium

题目描述

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

实现 SeatManager 类：

  • SeatManager(int n) 初始化一个 SeatManager 对象，它将管理从 1 到 n 编号的 n 个座位。所有座位最初都是可用的。
  • int reserve() 获取并预约编号最小的未预约座位，返回其编号。
  • void unreserve(int 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); // 初始化一个能管理5个座位的SeatManager。
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^5
  • 1 <= seatNumber <= n
  • 每次调用 reserve 时，都保证至少有一个座位未被预约。
  • 每次调用 unreserve 时，都保证 seatNumber 已被预约。
  • 总共最多调用 reserve 和 unreserve 方法 10^5 次。

解题思路

这道题要求我们设计一个座位预约管理系统，核心是要快速找到编号最小的可用座位，同时能够高效地释放座位。

思路分析：

最直观的想法是使用最小堆（优先队列）来存储所有可用的座位号。这样可以保证每次 reserve() 操作都能在 O(log n) 时间内获取到最小的座位号，unreserve() 操作也能在 O(log n) 时间内将座位重新加入可用列表。

具体实现：

  1. 初始化：将所有座位号（1到n）加入最小堆
  2. 预约座位：从堆顶取出最小的座位号并返回
  3. 释放座位：将释放的座位号重新加入堆中

优化思路： 初始时可以不将所有座位都加入堆中，而是维护一个 nextAvailable 指针，只有当有座位被释放时才加入堆。这样可以节省初始化时间和空间。

推荐解法： 使用最小堆存储可用座位，配合 nextAvailable 指针优化，既保证了效率又节省了空间。

代码实现

class SeatManager {
private:
    priority_queue<int, vector<int>, greater<int>> availableSeats;
    int nextAvailable;
    
public:
    SeatManager(int n) {
        nextAvailable = 1;
    }
    
    int reserve() {
        if (!availableSeats.empty()) {
            int seat = availableSeats.top();
            availableSeats.pop();
            return seat;
        }
        return nextAvailable++;
    }
    
    void unreserve(int seatNumber) {
        availableSeats.push(seatNumber);
    }
};

import heapq

class SeatManager:

    def __init__(self, n: int):
        self.available_seats = []
        self.next_available = 1

    def reserve(self) -> int:
        if self.available_seats:
            return heapq.heappop(self.available_seats)
        seat = self.next_available
        self.next_available += 1
        return seat

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

public class SeatManager {
    private PriorityQueue<int, int> availableSeats;
    private int nextAvailable;

    public SeatManager(int n) {
        availableSeats = new PriorityQueue<int, int>();
        nextAvailable = 1;
    }
    
    public int Reserve() {
        if (availableSeats.Count > 0) {
            return availableSeats.Dequeue();
        }
        return nextAvailable++;
    }
    
    public void Unreserve(int seatNumber) {
        availableSeats.Enqueue(seatNumber, seatNumber);
    }
}

var SeatManager = function(n) {
    this.availableSeats = [];
    this.nextAvailable = 1;
};

SeatManager.prototype.reserve = function() {
    if (this.availableSeats.length > 0) {
        this.availableSeats.sort((a, b) => a - b);
        return this.availableSeats.shift();
    }
    return this.nextAvailable++;
};

SeatManager.prototype.unreserve = function(seatNumber) {
    this.availableSeats.push(seatNumber);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
初始化O(1)O(1)
reserve()O(log k)O(k)
unreserve()O(log k)O(k)

其中 k 是已释放但尚未重新预约的座位数量。在最坏情况下，k 可能接近 n。

相关题目