每日一题|1845. 座位预约管理系统|最小堆操作、优先队列
本题需要满足如下两个操作:
1、 从一个队列中弹出最小值;
2、在一个队列中加入一个值;
3、高频操作100,000次使用。
综上使用优先队列是比较好的选择,对于python,优先队列可以使用一个最小堆来维护,所以是heapq包内的操作,代码量很小。代码如下:
class SeatManager(object):def __init__(self, n):""":type n: int"""self.seat_list = [i + 1 for i in range(n)]def reserve(self):""":rtype: int"""return heappop(self.seat_list)def unreserve(self, seatNumber):""":type seatNumber: int:rtype: None"""heappush(self.seat_list, seatNumber)# Your SeatManager object will be instantiated and called as such:
# obj = SeatManager(n)
# param_1 = obj.reserve()
# obj.unreserve(seatNumber)