Seat Reservation Manager

1. Define the problem

A cinema has seats numbered 1 to n and every seat starts free. Two things can happen: someone reserves a seat, and they must always be given the smallest free seat number , or someone gives a seat back, which makes that seat free again. To keep the input simple, this version takes n and a list of operations, where each operation is either ["reserve"] or ["unreserve", seatNumber]. Return an array holding the seat number handed out by each reserve operation, in order . A min-heap of free seat numbers answers both questions quickly: popping gives the smallest free seat, and pushing a returned seat puts it straight back into contention.

Constraints

1 ≤ n ≤ 10⁵
0 ≤ operations.length ≤ 10⁵
An unreserve operation is only ever given a seat that is currently taken

Example

Inputn = 5, operations = [["reserve"], ["reserve"], ["unreserve", 2], ["reserve"], ["reserve"]]

Output[1, 2, 2, 3]

Explanation The first reserve hands out seat 1 and the second hands out seat 2. Seat 2 is then given back, so it becomes the smallest free seat again and the third reserve hands out seat 2. The fourth reserve hands out seat 3.

2. Know the words first

In plain terms

Heap: A container that always knows its best item, where best means smallest or largest depending on how you set it up. Adding an item or taking the best item out costs about log n steps, and you never have to sort the whole collection.
Backing array: A heap is stored as one plain list. The item at position i keeps its parent at position (i - 1) / 2 rounded down, and its two children at positions 2i + 1 and 2i + 2. That is why every picture below is a row of numbered boxes.
Min-heap: A heap whose best item is the smallest one. Popping it always hands you the smallest value still inside.
Why not just sort: Sorting the free seats after every change would cost n log n each time. A heap keeps the smallest seat reachable while each change costs only about log n.

3. Visualize the solution

The row of boxes is the backing array of the min-heap of free seats, for n = 5

Statusbuild

Every seat from 1 to 5 starts free, so push all five into the min-heap.

What happens in this step

n = 5
backing array = [1, 2, 3, 4, 5]
reserved = []

Pushing seats in increasing order happens to give a sorted row here,
but that is a coincidence, not a promise of the heap.

Step 1 of 7

Steps to visualize

Each box is one slot of the list that stores the heap. Slot 0 always holds the smallest free seat.
A slot showing — is unused, because that many seats are currently taken.
A reserve pops slot 0. An unreserve pushes the returned seat back in.
The numbers in the other slots can look jumbled, and that is fine: a heap only promises that a parent is smaller than its children, not that the whole row is sorted.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

The row of boxes is the backing array of the min-heap of free seats, for n = 5

Statusbuild

Every seat from 1 to 5 starts free, so push all five into the min-heap.

What happens in this step

n = 5
backing array = [1, 2, 3, 4, 5]
reserved = []

Pushing seats in increasing order happens to give a sorted row here,
but that is a coincidence, not a promise of the heap.

Step 1 of 7

5. Solution

Solution

solution.tsTypeScript

function seatReservations(n, operations) {
  const free = new Heap((a, b) => a - b);

  for (let seat = 1; seat <= n; seat++) {
    free.push(seat);
  }

  const reserved = [];

  for (const operation of operations) {
    if (operation[0] === 'reserve') {
      reserved.push(free.pop());
    } else {
      free.push(operation[1]);
    }
  }

  return reserved;
}

class Heap {
  constructor(compare) {
    this.items = [];
    this.compare = compare;
  }

  size() {
    return this.items.length;
  }

  peek() {
    return this.items[0];
  }

  push(value) {
    this.items.push(value);
    let child = this.items.length - 1;

    while (child > 0) {
      const parent = (child - 1) >> 1;
      if (this.compare(this.items[child], this.items[parent]) >= 0) break;
      const swap = this.items[child];
      this.items[child] = this.items[parent];
      this.items[parent] = swap;
      child = parent;
    }
  }

  pop() {
    const top = this.items[0];
    const last = this.items.pop();

    if (this.items.length > 0) {
      this.items[0] = last;
      let parent = 0;

      while (true) {
        const left = parent * 2 + 1;
        const right = parent * 2 + 2;
        let best = parent;

        if (left < this.items.length && this.compare(this.items[left], this.items[best]) < 0) best = left;
        if (right < this.items.length && this.compare(this.items[right], this.items[best]) < 0) best = right;
        if (best === parent) break;

        const swap = this.items[parent];
        this.items[parent] = this.items[best];
        this.items[best] = swap;
        parent = best;
      }
    }

    return top;
  }
}

Time: O((n + m) log n) for n seats and m operations
Space: O(n)

6. Test cases

Test cases

Input	Expected	Covers
`n = 5, operations = [["reserve"], ["reserve"], ["unreserve", 2], ["reserve"], ["reserve"]]`	`[1, 2, 2, 3]`	example from the docstring
`n = 2, operations = [["reserve"], ["reserve"]]`	`[1, 2]`	every seat gets taken, no seat is given back
`n = 1, operations = [["reserve"], ["unreserve", 1], ["reserve"]]`	`[1, 1]`	smallest cinema, the only seat is reused
`n = 3, operations = [reserve, reserve, reserve, unreserve 1, unreserve 3, reserve]`	`[1, 2, 3, 1]`	two seats come back and the smaller one is handed out first
`n = 4, operations = []`	`[]`	nothing happens at all
`n = 5, operations = [reserve, reserve, reserve, unreserve 2, reserve]`	`[1, 2, 3, 2]`	a returned seat beats the untouched higher seats

Seat Reservation Manager