Skip to content

1845. Seat Reservation Manager 👍

  • Time:
    • Constructor: $O(1)$ (C++/Java) | $O(n\log n)$ (Python)
    • reserver(): $O(\log n)$
    • unreserve(seatNumber: int): $O(\log n)$
  • Space:
    • Constructor: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class SeatManager {
 public:
  SeatManager(int n) {}

  int reserve() {
    if (minHeap.empty())
      return ++num;

    const int minNum = minHeap.top();
    minHeap.pop();
    return minNum;
  }

  void unreserve(int seatNumber) {
    minHeap.push(seatNumber);
  }

 private:
  priority_queue<int, vector<int>, greater<>> minHeap;
  int num = 0;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class SeatManager {
  public SeatManager(int n) {}

  public int reserve() {
    if (minHeap.isEmpty())
      return ++num;
    return minHeap.poll();
  }

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

  private Queue<Integer> minHeap = new PriorityQueue<>();
  private int num = 0;
}

1
2
3
4
5
6
7
8
9
class SeatManager:
  def __init__(self, n: int):
    self.minHeap = [i + 1 for i in range(n)]

  def reserve(self) -> int:
    return heapq.heappop(self.minHeap)

  def unreserve(self, seatNumber: int) -> None:
    heapq.heappush(self.minHeap, seatNumber)