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, greater> availableSeats;SeatManager(int n) {for (int seatNumber = 1; seatNumber reserve(); * obj->unreserve(seatNumber); */