Practice/Meta/Leetcode 1845. Seat Reservation Manager

Leetcode 1845. Seat Reservation Manager

CodingOptional

Problem

Design a system to manage seat reservations for a theater with n seats numbered from 1 to n. Initially, all seats are available for booking.

Your system must support two operations:

• reserve(): Book the lowest-numbered available seat, mark it as reserved, and return its number
• unreserve(seatNumber): Mark the specified seat as available again

The system must efficiently handle up to 100,000 operations in total, so your implementation should prioritize performance for both operations.

Requirements

1. Implement a SeatManager class that takes n (total number of seats) as a constructor parameter
2. The reserve() method should return the smallest available seat number and mark it as reserved
3. The unreserve(seatNumber) method should make the specified seat available again
4. All seats are initially available (numbered 1 through n)
5. You may assume that reserve() is only called when at least one seat is available
6. You may assume that unreserve() is only called for seats that are currently reserved

Constraints

• 1 ≤ n ≤ 100,000
• 1 ≤ seatNumber ≤ n
• At most 100,000 calls total to reserve() and unreserve()
• reserve() is only called when there is at least one unreserved seat
• unreserve() is only called with a seat that is currently reserved
• Time complexity should be O(log n) or better for each operation

Examples

Example 1:

SeatManager seatManager = new SeatManager(5); seatManager.reserve(); // Returns 1 (smallest available) seatManager.reserve(); // Returns 2 (smallest available) seatManager.unreserve(2); // Seat 2 becomes available seatManager.reserve(); // Returns 2 (smallest available) seatManager.reserve(); // Returns 3 (smallest available) seatManager.reserve(); // Returns 4 (smallest available) seatManager.unreserve(5); // Does nothing since seat 5 was never reserved

Example 2:

SeatManager seatManager = new SeatManager(3); seatManager.reserve(); // Returns 1 seatManager.reserve(); // Returns 2 seatManager.reserve(); // Returns 3 seatManager.unreserve(1); // Seat 1 becomes available seatManager.unreserve(3); // Seat 3 becomes available seatManager.reserve(); // Returns 1 (smallest available, not 3)