LeetCode 1845: Seat Reservation Manager Solution

Master LeetCode problem 1845 (Seat Reservation Manager), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1845. Seat Reservation Manager

Medium

Design Heap (Priority Queue)

Problem Explanation

Explanation

To solve this problem, we can use a min heap to keep track of the available seats. When a seat is reserved, we pop the smallest seat number from the heap. When a seat is unreserved, we add the seat number back to the heap.

Algorithm:

Initialize a min heap to store available seats.
Initialize a counter to keep track of the next available seat number.
In the constructor, populate the min heap with seat numbers from 1 to n.
In the reserve() method, pop the top of the min heap and return the seat number.
In the unreserve() method, add the seat number back to the min heap.

Time Complexity:

Reserve operation: O(log n) where n is the number of seats.
Unreserve operation: O(log n)
Overall time complexity for n reserve and unreserve operations: O(n log n)

Space Complexity:

O(n) for storing the heap.

Solution Code

import java.util.PriorityQueue;

class SeatManager {
    PriorityQueue<Integer> availableSeats;
    
    public SeatManager(int n) {
        availableSeats = new PriorityQueue<>();
        for (int i = 1; i <= n; i++) {
            availableSeats.add(i);
        }
    }
    
    public int reserve() {
        return availableSeats.poll();
    }
    
    public void unreserve(int seatNumber) {
        availableSeats.add(seatNumber);
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1845 (Seat Reservation Manager)?

This page provides optimized solutions for LeetCode problem 1845 (Seat Reservation Manager) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1845 (Seat Reservation Manager)?

The time complexity for LeetCode 1845 (Seat Reservation Manager) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1845 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1845 in Java, C++, or Python.

Back to LeetCode Solutions