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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Exam Room

Difficulty: Medium

Problem Description

There is an exam room with n seats in a single row labeled from 0 to n - 1. When a student enters the room, they must sit in the seat that maximizes the distance to the closest person. If there are multiple such seats, they sit in the seat with the lowest number. If no one is in the room, then the student sits at seat number 0. Design a class that simulates the mentioned exam room.

Implement the ExamRoom class:

  • ExamRoom(int n) Initializes the object of the exam room with the number of the seats n.
  • int seat() Returns the label of the seat at which the next student will set.
  • void leave(int p) Indicates that the student sitting at seat p will leave the room. It is guaranteed that there will be a student sitting at seat p.

Key Insights

  • The goal is to maximize the distance to the nearest occupied seat when a student sits down.
  • Seats should be filled in a way that is efficient in terms of both time and space.
  • A priority queue (or max heap) can be used to efficiently determine the best seat to occupy.
  • Keeping track of the occupied seats allows for easy updates when a student leaves.

Space and Time Complexity

Time Complexity: O(log k) for seating a student where k is the number of occupied seats, and O(1) for leaving a seat. Space Complexity: O(k) for storing the occupied seats.

Solution

To solve the problem, we can use a max heap (priority queue) to keep track of the distances between occupied seats. When a student enters, we calculate the maximum distance from each occupied seat and push this information into the heap. The seat with the maximum distance is selected, and when a student leaves, we update the heap accordingly.

  1. Store the occupied seats in a sorted list or set to facilitate easy distance calculation.
  2. Use a max heap to prioritize the best seats based on the distance to the nearest occupied seat.
  3. When a student leaves, adjust the distances and update the heap.

Code Solutions

import heapq

class ExamRoom:

    def __init__(self, n: int):
        self.n = n
        self.seats = []
        self.available = []
        self.last_seat = -1

    def seat(self) -> int:
        if not self.seats:
            self.seats.append(0)
            return 0
        
        max_distance = 0
        seat_to_take = 0
        
        for i in range(len(self.seats)):
            if i == 0:
                distance = self.seats[i] - 0
            else:
                distance = (self.seats[i] - self.seats[i - 1]) // 2
            
            if distance > max_distance:
                max_distance = distance
                seat_to_take = self.seats[i - 1] + distance
            
        if self.seats[-1] != self.n - 1:
            distance = self.n - 1 - self.seats[-1]
            if distance > max_distance:
                seat_to_take = self.n - 1
        
        self.seats.append(seat_to_take)
        self.seats.sort()
        return seat_to_take

    def leave(self, p: int) -> None:
        self.seats.remove(p)
← Back to All Questions