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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Seat Reservation Manager

Number: 1955

Difficulty: Medium

Paid? No

Companies: Google, Meta, Dropbox

Problem Description

Design a system that manages the reservation state of n seats numbered from 1 to n. The system should support reserving the smallest-numbered available seat and unreserving a seat by its number.

Key Insights

  • Use a min-heap (priority queue) to efficiently track the smallest available seat.
  • On initialization, push all seats (from 1 to n) into the heap.
  • Reserving involves popping the minimum element, which guarantees the smallest available seat.
  • Unreserving involves pushing the seat number back onto the heap.
  • Both reserve and unreserve operations run in O(log n) time.

Space and Time Complexity

Time Complexity:

  • reserve: O(log n)
  • unreserve: O(log n)

Space Complexity: O(n) because we keep all seat numbers in a min-heap.

Solution

We maintain a min-heap to store all currently available seat numbers. Initially, all seats (1 to n) are available, so we push all of them into the heap. When a reserve() call is made, the smallest available seat is popped from the heap and returned as reserved. Conversely, when unreserve(seatNumber) is called, the seat number is pushed back into the heap to mark it as available again. This structure ensures that both operations perform efficiently under the given constraints.

Code Solutions

Below are the implementations in Python, JavaScript, C++, and Java.

import heapq

class SeatManager:
    def __init__(self, n: int):
        # Initialize a min-heap with all seat numbers from 1 to n.
        self.available_seats = list(range(1, n+1))
        heapq.heapify(self.available_seats)  # Turn the list into a heap.

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

    def unreserve(self, seatNumber: int) -> None:
        # Push the seat number back to the heap to mark it as available.
        heapq.heappush(self.available_seats, seatNumber)

# Example usage:
# seatManager = SeatManager(5)
# print(seatManager.reserve())    # Output: 1
# seatManager.unreserve(2)
← Back to All Questions