Problem statement

A venue has n seats numbered 1 to n, all free at the start. Design the system that hands them out.

Write the class SeatManager:

• SeatManager(int n) sets up n free seats.
• int reserve() reserves the smallest-numbered free seat and returns its number.
• void unreserve(int seatNumber) makes the reserved seat seatNumber free again.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.

Example 1

Input: ["SeatManager","reserve","reserve","unreserve","reserve","reserve","reserve","reserve","unreserve"]
[[5],[],[],[2],[],[],[],[],[5]]
Output: [null,1,2,null,2,3,4,5,null]
Explanation: Seats 1 and 2 are handed out; 2 is returned, so the next reserve gives 2 again, then 3, 4 and 5. Seat 5 is then returned.

Example 2

Input: ["SeatManager","reserve","reserve","reserve","unreserve","unreserve","reserve"]
[[3],[],[],[],[3],[1],[]]
Output: [null,1,2,3,null,null,1]
Explanation: All three seats are taken, then 3 and 1 come back. The smallest free seat is 1.

Constraints

• 1 <= n <= 10^5
• 1 <= seatNumber <= n
• reserve is only called while at least one seat is free
• unreserve is only called on a reserved seat
• At most 10^5 calls are made to reserve and unreserve in total

Hints for Seat Reservation Manager

1. Hint 1

   Scanning from seat 1 for a free one is O(n) per call. Which seats can actually be the answer?

2. Hint 2

   Seats never touched so far are always the block next, next + 1, …, n; the only other free seats are ones that were returned.

3. Hint 3

   Keep next (the first untouched seat) and a min-heap of returned seats. Every returned seat is smaller than next, so reserve pops the heap when it is non-empty and otherwise hands out next++; unreserve pushes onto the heap.

How to solve Seat Reservation Manager

Split the free seats into two groups: the untouched tail next..n, described by one integer, and the seats that were returned, kept in a min-heap.

Approach

1. Start with next = 1 and an empty min-heap.
2. reserve(): if the heap is not empty, pop and return its minimum; otherwise return next and increase it.
3. unreserve(s): push s onto the heap.

Why it works

Seats are handed out from the tail in increasing order, so every seat that was ever reserved — and therefore every returned seat — is smaller than next. Hence when the heap holds anything its minimum is the smallest free seat overall, and when it is empty the smallest free seat is next. (Calling reserve with no free seat is ruled out, so next never passes n.)

Complexity

• Time — O(log k) per call, where k is the number of returned seats waiting
• Space — O(k) — never a table of all n seats

Pitfalls

• Pushing all n seats into the heap up front works but costs O(n log n) — or O(n) memory — before the first call.
• A max-heap or a plain stack of returned seats hands out the wrong seat when several are returned out of order.

Reference solution

Python

import heapq

class SeatManager:

    def __init__(self, n: int):
        self.next = 1      # seats next..n were never handed out
        self.returned = [] # min-heap of seats given back, all < next

    def reserve(self) -> int:
        if self.returned:
            return heapq.heappop(self.returned)
        self.next += 1
        return self.next - 1

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

Java

class SeatManager {
    private int next = 1; // seats next..n were never handed out
    private PriorityQueue<Integer> returned = new PriorityQueue<>(); // all < next

    public SeatManager(int n) {
    }

    public int reserve() {
        return returned.isEmpty() ? next++ : returned.poll();
    }

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

C++

class SeatManager {
    int next = 1; // seats next..n were never handed out
    priority_queue<int, vector<int>, greater<int>> returned; // all < next
public:
    SeatManager(int n) {}

    int reserve() {
        if (returned.empty()) return next++;
        int s = returned.top();
        returned.pop();
        return s;
    }

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

JavaScript

var SeatManager = function(n) {
    this.next = 1;  // seats next..n were never handed out
    this.heap = []; // min-heap of seats given back, all < next
};

SeatManager.prototype.reserve = function() {
    var h = this.heap;
    if (h.length === 0) return this.next++;
    var top = h[0], last = h.pop();
    if (h.length) {
        var i = 0;
        for (;;) {
            var l = 2 * i + 1, r = l + 1, m = i;
            if (l < h.length && h[l] < (m === i ? last : h[m])) m = l;
            if (r < h.length && h[r] < (m === i ? last : h[m])) m = r;
            if (m === i) break;
            h[i] = h[m];
            i = m;
        }
        h[i] = last;
    }
    return top;
};

SeatManager.prototype.unreserve = function(seatNumber) {
    var h = this.heap, i = h.length;
    h.push(seatNumber);
    while (i > 0 && h[(i - 1) >> 1] > seatNumber) { h[i] = h[(i - 1) >> 1]; i = (i - 1) >> 1; }
    h[i] = seatNumber;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More heap problems

• Design Task Manager Medium
• Design a Food Rating System Medium
• Design a Number Container System Medium
• Smallest Number in Infinite Set Medium
• Stock Price Fluctuation Medium
• Design Twitter Medium