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);
 */