Problem 415466 · medium · Phase 04 Non-Linear Data Structures

Cinema Seat Desk

heaps · classes · lazy allocation · min-heap

A cinema has seats numbered 1 to n. Write a class SeatDesk that hands out seats:

  • SeatDesk(n) starts with every seat free.
  • reserve() reserves and returns the smallest-numbered free seat. It is only called when at least one seat is free.
  • unreserve(seat) frees the given seat. It is only called on a seat that is currently reserved.

n can be as large as 10**6 while only a few thousand operations happen, so do not build a list of all n seats in the constructor.

Examples

Input:  ops  = ["SeatDesk", "reserve", "reserve", "unreserve", "reserve", "reserve"]
        args = [[5], [], [], [1], [], []]
Output: [None, 1, 2, None, 1, 3]
Explanation: seats 1 and 2 are taken, seat 1 is released and is the smallest free seat again,
             then seat 3 is the next free one.

Constraints

  • 1 <= n <= 10**6, at most 10**5 calls in total
  • Target complexity: O(1) constructor, O(log n) per reserve and unreserve.

Goals

  • Hand out the smallest free seat without materialising all seats up front
  • Recycle released seats through a min-heap
  • Combine a counter for never-issued seats with a heap of returned ones
Starting Python…