[LeetCode] 1845. Seat Reservation Manager

Design a system that manages the reservation state of n seats that are numbered from 1 to n.

Implement the SeatManager class:

• SeatManager(int n) Initializes a SeatManager object that will manage n seats numbered from 1 to n. All seats are initially available.
• int reserve() Fetches the smallest-numbered unreserved seat, reserves it, and returns its number.
• void unreserve(int seatNumber) Unreserves the seat with the given seatNumber.

Example 1:
Input
[“SeatManager”, “reserve”, “reserve”, “unreserve”, “reserve”, “reserve”, “reserve”, “reserve”, “unreserve”]
[[5], [], [], [2], [], [], [], [], [5]]
Output
[null, 1, 2, null, 2, 3, 4, 5, null]

Explanation
SeatManager seatManager = new SeatManager(5); // Initializes a SeatManager with 5 seats.
seatManager.reserve(); // All seats are available, so return the lowest numbered seat, which is 1.
seatManager.reserve(); // The available seats are [2,3,4,5], so return the lowest of them, which is 2.
seatManager.unreserve(2); // Unreserve seat 2, so now the available seats are [2,3,4,5].
seatManager.reserve(); // The available seats are [2,3,4,5], so return the lowest of them, which is 2.
seatManager.reserve(); // The available seats are [3,4,5], so return the lowest of them, which is 3.
seatManager.reserve(); // The available seats are [4,5], so return the lowest of them, which is 4.
seatManager.reserve(); // The only available seat is seat 5, so return 5.
seatManager.unreserve(5); // Unreserve seat 5, so now the available seats are [5].

Constraints:
1 <= n <= 105
1 <= seatNumber <= n
For each call to reserve, it is guaranteed that there will be at least one unreserved seat.
For each call to unreserve, it is guaranteed that seatNumber will be reserved.
At most 105 calls in total will be made to reserve and unreserve.

座位预约管理系统。

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/seat-reservation-manager
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路一 - 贪心

既然是要返回可以预约座位的最小编号，那么我们可以考虑用一个最小堆存放还未被使用过的座位编号。一开始，堆中存放了所有的座位编号，当有人开始就坐，我们就按座位号从小到大分发座位。谁离开了座位，他的座位号也会被回收到最小堆的堆顶。再有新的人来坐，那么最小的座位号还是会被优先分发。

复杂度

时间O(nlogn)
空间O(n)

代码

Java实现

class SeatManager {
	PriorityQueue<Integer> minHeap;

	public SeatManager(int n) {
		minHeap = new PriorityQueue<>();
		for (int i = 1; i <= n; i++) {
			minHeap.offer(i);
		}
	}

	public int reserve() {
		if (!minHeap.isEmpty()) {
			return minHeap.poll();
		}
		return -1;
	}

	public void unreserve(int seatNumber) {
		minHeap.offer(seatNumber);
	}
}

/**
 * Your SeatManager object will be instantiated and called as such:
 * SeatManager obj = new SeatManager(n);
 * int param_1 = obj.reserve();
 * obj.unreserve(seatNumber);
 */

思路二 - 优化过了的贪心

注意 input 数据如果很大的话，把所有数字都放到堆中的做法就不是很聪明。我们可以换一个思路，假设没有任何人坐下之前，屋子里是没有椅子的，当有人开始进来坐下的时候，如果此时没有可用的椅子，我们就加一把椅子；如果有人离开，人可以离开但是椅子再也不离开了，那么再有新的人进来的时候，直接坐空着的椅子就好了。

这里我们还是需要一个最小堆，存放的是此时没有人坐的椅子。如果堆为空，说明没有椅子可用，椅子数要加一；当有人离开的时候，把此人的椅子编号再放回最小堆即可。

复杂度

时间O(nlogn)
空间O(n)

代码

Java实现

class SeatManager {
    PriorityQueue<Integer> queue;
    int seats;

    public SeatManager(int n) {
        queue = new PriorityQueue<>();
        seats = 0;
    }
    
    public int reserve() {
        if (!queue.isEmpty()) {
            return queue.poll();
        }
        return ++seats;
    }
    
    public void unreserve(int seatNumber) {
        queue.offer(seatNumber);
    }
}

/**
 * Your SeatManager object will be instantiated and called as such:
 * SeatManager obj = new SeatManager(n);
 * int param_1 = obj.reserve();
 * obj.unreserve(seatNumber);
 */