We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Seat Reservation Manager

Difficulty: Medium

Problem Description

Design a system that manages the reservation state of n seats that are numbered from 1 to n. Implement the SeatManager class with methods to reserve and unreserve seats.

Key Insights

  • The problem requires managing a dynamic list of available and reserved seats.
  • Efficient retrieval of the smallest unreserved seat is crucial.
  • Unreserving a seat should be quick and straightforward.
  • A min-heap (priority queue) can be effectively used to manage available seats.

Space and Time Complexity

Time Complexity:

  • reserve(): O(log k) where k is the number of unreserved seats.
  • unreserve(seatNumber): O(log k) for adding the seat back to the available seats.

Space Complexity: O(n) for storing the seats.

Solution

To solve this problem, we can use a min-heap (priority queue) to keep track of the available seats. When reserving a seat, we extract the minimum element from the heap, which represents the smallest unreserved seat. When unreserving a seat, we push the seat number back into the heap. This allows us to efficiently manage the state of reserved and unreserved seats.

Code Solutions

import heapq

class SeatManager:
    def __init__(self, n: int):
        # Initialize a min-heap and push all seat numbers into it.
        self.available_seats = list(range(1, n + 1))
        heapq.heapify(self.available_seats)

    def reserve(self) -> int:
        # Pop the smallest seat number from the heap.
        return heapq.heappop(self.available_seats)

    def unreserve(self, seatNumber: int) -> None:
        # Push the unreserved seat number back into the heap.
        heapq.heappush(self.available_seats, seatNumber)
← Back to All Questions