1845. 座位预约管理系统

Problem: 1845. 座位预约管理系统

思路

首先想到的是使用最小堆来模拟，因为题目的reserve返回的是最小可预约座位，并把座位变为不可预约。如果用最小堆来维护可预约座位，那么reserve操作就是出堆操作；unreserve就是入堆操作。出入堆操作时间复杂度为$O(logn)$。

但是如果n太大，初始化操作就会消耗太多的时间。我们可以用逆向思维：如果我们维护曾经被预约过，又被释放的座位，就不需要初始化操作。当执行预约操作时，如果堆里有座位，就将执行出堆操作。否则返回已被预约的座位数+1；当执行取消预约时，将该座位入堆。

优化的方法参考灵茶山艾府

复杂度

• 时间复杂度: 初始化$O(1)$,reserve和unreserve为$O(log q)$，q为reserve的调用次数。
• 空间复杂度: $O(q)$。

Code

class SeatManager {
    private final PriorityQueue<Integer> available = new PriorityQueue<>();
    private int seats;

    public SeatManager(int n) {
    }

    public int reserve() {
        if (!available.isEmpty()) { // 有空出来的椅子
            return available.poll(); // 坐编号最小的
        }
        return ++seats; // 添加一把新的椅子
    }

    public void unreserve(int seatNumber) {
        available.add(seatNumber); // 有人离开了椅子
    }
}