Practice/Google/Leetcode 3140. Consecutive Available Seats II

Leetcode 3140. Consecutive Available Seats II

CodingOptional

Problem

Design a dynamic seat reservation system for a theater with a single row of numbered seats. The system must efficiently handle three operations:

1. Reserve a seat: Mark a specific seat as occupied
2. Release a seat: Mark a specific seat as available again
3. Find consecutive seats: Locate k consecutive available seats and return their positions

The theater has seats numbered from 1 to n, and all seats begin as available. When finding consecutive seats, you should return the leftmost valid range of seat numbers. If no such range exists, return an empty list.

Requirements

1. Implement a SeatManager class that maintains the state of all seats
2. The reserve(seat) method should mark a seat as occupied and return True if successful, False if the seat was already occupied
3. The release(seat) method should mark a seat as available and return True if successful, False if the seat was already free
4. The findConsecutive(k) method should return a list of k consecutive seat numbers that are all available, or an empty list if impossible
5. When multiple valid ranges of k consecutive seats exist, return the leftmost one (starting with the smallest seat number)
6. All operations should be handled efficiently to support frequent updates and queries

Constraints

• 1 ≤ n ≤ 10^5 (number of seats)
• 1 ≤ seat ≤ n (seat numbers are within valid range)
• 1 ≤ k ≤ n (number of consecutive seats requested)
• At most 10^5 total operations will be performed
• Target time complexity: O(log n) per operation for efficient solutions

Examples

Example 1:

Theater with 10 seats, all initially available Operations: reserve(3) → True (seat 3 now occupied) reserve(5) → True (seat 5 now occupied) findConsecutive(2) → [1, 2] (leftmost pair of consecutive free seats)

Example 2:

Theater with 5 seats Operations: reserve(2) → True reserve(3) → True reserve(4) → True findConsecutive(3) → [] (no 3 consecutive seats available) release(3) → True findConsecutive(3) → [1, 2, 3] (after releasing seat 3, we have a block of 3)

Example 3:

Theater with 8 seats Operations: findConsecutive(4) → [1, 2, 3, 4] (first 4 seats available) reserve(2) → True findConsecutive(4) → [4, 5, 6, 7] (need to skip past seat 2) release(2) → True findConsecutive(4) → [1, 2, 3, 4] (back to original best option)