06.11.2023
1845. Seat Reservation Manager medium
blog post
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 expose the heap directly)
Complexity
Time complexity:
O(log(n)) for operationsSpace 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)
}
}