LeetCode Entry

1845. Seat Reservation Manager

06.11.2023 medium 2023 kotlin

Design reservation number system

1845. Seat Reservation Manager medium blog post substack image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/395

Problem TLDR

Design reservation number system

Intuition

The naive approach is to just use PriorityQueue as is:

class SeatManager(n: Int): PriorityQueue<Int>() {
  init { for (x in 1..n) add(x) }
  fun reserve() = poll()
  fun unreserve(seatNumber: Int) = add(seatNumber)
}

However, we can improve the memory cost by noticing, that we can shrink the heap when max is returned.

Approach

  • we can save some lines of code by using extending the class (prefer a field instead in a production code to not exprose the heap directly)

Complexity

  • Time complexity: \(O(log(n))\) for operations

  • Space complexity: \(O(n)\)

Code


class SeatManager(n: Int): PriorityQueue<Int>() {
  var max = 0
  fun reserve() = if (isEmpty()) ++max else poll()
  fun unreserve(seatNumber: Int) {
    if (seatNumber == max) max--
    else add(seatNumber)
  }
}