Exam Room - Leetcode Solution

The Exam Room problem on LeetCode is a problem that asks you to design a class for an exam room that has the following functionalities:

1. The class should have a constructor that takes in an integer N, representing the number of seats in the exam room.

2. The class should have a method called seat() that returns an integer representing the seat number that the next student should sit in. This method should also update the state of the exam room to mark the seat as occupied.

3. The class should have a method called leave(seat) that takes in an integer representing the seat number of a student who is leaving the exam room. This method should update the state of the exam room to mark the seat as unoccupied.

The solution to this problem involves implementing the seat() and leave() methods in a way that efficiently finds the seat that the next student should sit in and updates the state of the exam room accordingly.

One possible solution for this problem is to use a priority queue to store the seats in the exam room. The priority queue should be sorted based on the distance between the seats, with the seats that are farthest apart being at the top of the queue.

When a student wants to sit in the exam room, the seat() method should first check if there are any seats already occupied. If there are, it should dequeue the seat that is farthest away from any other occupied seat and return that seat number. If there are no occupied seats, it should return seat 0.

Once a student has been assigned a seat, the seat() method should update the state of the exam room by marking the seat as occupied and adding it to the priority queue.

When a student leaves the exam room, the leave() method should remove the seat from the priority queue and mark it as unoccupied in the state of the exam room.

Here is the implementation of the ExamRoom class using a priority queue:

import heapq

class ExamRoom:
    def __init__(self, N: int):
        self.N = N
        self.seats = []
        heapq.heappush(self.seats, (-self.N, -1, self.N))   # priority queue

    def seat(self) -> int:
        # Pop the seat farthest away from any taken seats
        seat_distance, seat_start, seat_end = heapq.heappop(self.seats)
        if seat_start == -1:
            seat = 0
        elif seat_end == self.N:
            seat = self.N-1
        else:
            seat = (seat_start + seat_end) // 2
        
        # Insert new segments
        left_segment = (seat_start, seat)
        right_segment = (seat, seat_end)
        for segment in [left_segment, right_segment]:
            segment_distance = -min(segment[0], self.N-segment[1])
            heapq.heappush(self.seats, (segment_distance, segment[0], segment[1]))
        
        return seat

    def leave(self, p: int) -> None:
        # Find and delete the left and right segments that p belongs to
        for i, (distance, start, end) in enumerate(self.seats):
            if start == p:
                left_segment = (start, start + end - 2*start)
                right_segment = (start + end - 2*start, end)
                del self.seats[i]
                break
            elif end == p:
                left_segment = (start, end - start)
                right_segment = (end - start, end)
                del self.seats[i]
                break

        # Remove segments from priority queue
        self.seats = [(distance, start, end) for (distance, start, end) in self.seats if start != p and end != p]

        # Add new segment
        new_segment = (left_segment[0], right_segment[1])
        distance = -min(new_segment[0], self.N-new_segment[1])
        heapq.heappush(self.seats, (distance, new_segment[0], new_segment[1]))

In the constructor, we initialize a priority queue with a single segment representing the entire exam room. We use negative distances in the priority queue so that the segments that are farthest apart are at the top of the queue.

In the seat() method, we pop the segment with the farthest distance and compute the seat number based on the midpoint of that segment. We then insert two new segments to represent the seats on either side of the newly occupied seat, and add them to the priority queue.

In the leave() method, we first find the left and right segments that the student was sitting in, delete them from the priority queue, and update the state of the exam room to mark the seat as unoccupied. We then combine the left and right segments into a single larger segment, add it to the priority queue, and sort the queue based on the distances between the segments.

Overall, this solution has a time complexity of O(log N) for the seat() method (due to the use of a priority queue) and O(N) for the leave() method (due to the need to search for the segments to delete). The space complexity is O(N) for the priority queue.

1