Seat Reservation Desk
MediumHeap / Priority Queue
Problem
A theatre has seats numbered 1 to n, all initially free. The box office processes a list of operations: ops[i] is "reserve", which books the lowest-numbered free seat and reports its number, or "release", which frees the reserved seat vals[i] (for "reserve", vals[i] is 0 and ignored).
Return the seat numbers reported by the "reserve" operations, in order.
Example 1
- Input:
- n = 5, ops = ["reserve", "reserve", "release", "reserve", "reserve"], vals = [0, 0, 1, 0, 0]
- Output:
- [1, 2, 1, 3]
Seats 1 and 2 are booked, seat 1 is freed, so the next reserve gets 1 again and the one after gets 3.
Example 2
- Input:
- n = 3, ops = ["reserve", "reserve", "reserve", "release", "release", "reserve"], vals = [0, 0, 0, 3, 2, 0]
- Output:
- [1, 2, 3, 2]
Constraints
- 1 ≤ n ≤ 10^5
- 1 ≤ ops.length ≤ 10^5
- Every "reserve" happens when at least one seat is free.
- Every "release" names a seat that is currently reserved.
Hint
Show the first hint
A min-heap of all free seats works, but building it costs O(n) even if only a few operations happen. Can you avoid storing seats that were never touched?
Walkthrough
How to approach it
01Clarify before coding
- Is the lowest-numbered free seat always the one reserved? Yes.
- Can a free seat be released? No, releases only name reserved seats.
- Is it a class in disguise? Yes: a constructor (n), reserve() and release(seat). We model it as an operations list.
02Brute force
Keep a boolean array of seats and scan from seat 1 for the first free one on every reserve.
Cost: O(n) per reserve, so O(n · q) = 10^10 in the worst case.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.