568. Seat Desk

MediumHeapDesignOrdered Set3 hints
RPby Rohit Parihar

A ticket desk manages n numbered seats, 1 through n, and every seat starts out free. Implement the class SeatDesk:

  • SeatDesk(int n) creates the desk with seats 1..n all free.
  • int reserve() reserves the free seat with the smallest number and returns that number.
  • void unreserve(int seat) makes a previously reserved seat free again, so it can be handed out later.

Calls are always valid: reserve is only called when at least one seat is free, and unreserve is only called with a seat that is currently reserved. Each operation should run in O(log n) time or better, with O(n) total space.

Example 1

Input:
operations = ["SeatDesk","reserve","reserve","reserve","unreserve","reserve"]arguments = [[4],[],[],[],[2],[]]
Output:
[null,1,2,3,null,2]
Explanation:

Seats 1, 2, 3 are handed out; after seat 2 is released, the next reserve returns 2 again, the smallest free seat.

Example 2

Input:
operations = ["SeatDesk","reserve","unreserve","reserve"]arguments = [[1],[],[1],[]]
Output:
[null,1,null,1]
Explanation:

With a single seat, releasing it makes it available again.

Example 3

Input:
operations = ["SeatDesk","reserve","reserve","unreserve","unreserve","reserve","reserve","reserve"]arguments = [[3],[],[],[2],[1],[],[],[]]
Output:
[null,1,2,null,null,1,2,3]
Explanation:

Seats 2 then 1 are released, but reserve always returns the smallest free one first: 1, 2, then the untouched seat 3.

Constraints

  • 1 ≤ n ≤ 100000
  • At most 100000 calls in total to reserve and unreserve.
  • 1 ≤ seat ≤ n, and the seat is currently reserved.
  • reserve is only called while a free seat exists.

How this problem is judged

Answers
Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Input
Each case is an operation log. operations names the class first and then each method call; arguments holds the arguments for each, in the same order. Your answer is one list with a result per operation - null for the constructor and for methods that return nothing.

Expected complexity

Time
O(log n) per operation
Space
O(n)

What the author was aiming for. Your own solution is not measured against it.

Asked in an interview

Were you asked this in an interview? Say where, anonymously.

Code
Loading the editor…

operations names the class, then each method to call; arguments holds one list of arguments per operation, in the same order.