Leetcode Daily Challenge 1845. Seat Reservation Manager

1845. Seat Reservation Manager

题目要求：初始化一个SeatManager类包括默认构造函数和类函数，所有的seat初始化为true。reverse函数返回最小的true，然后把这个编号的椅子赋值为false。unreverse(seatNumber)函数把编号为seatNumber的椅子恢复成true。

思路

本来想用常规的循环，每次reverse就搜索最小值，时间复杂度是O(n*m)，会超时。因此考虑采用优先队列，每次会自动排序，队列的top就是可用的最小值，用完之后pop()。如果unreverse则把seatNumber push到优先队列中。

class SeatManager {
public:priority_queue<int, vector<int>, greater<int>> availableSeats;SeatManager(int n) {for (int seatNumber = 1; seatNumber <= n; ++seatNumber) {availableSeats.push(seatNumber);}}int reserve() {int seatNumber = availableSeats.top();availableSeats.pop();return seatNumber;}void unreserve(int seatNumber) {availableSeats.push(seatNumber);}
};/*** Your SeatManager object will be instantiated and called as such:* SeatManager* obj = new SeatManager(n);* int param_1 = obj->reserve();* obj->unreserve(seatNumber);*/