#855

Medium

auto_awesomeDesign plus Heap (Priority Queue)

LeetCode Problem Workspace

Exam Room

Simulate an exam room where each student chooses a seat maximizing distance to others, using design plus heap structures efficiently.

design heap priority queue ordered set

Problem Statement

You are asked to design a class for an exam room with n seats arranged in a single row labeled 0 to n - 1. When a student enters, they must choose a seat that maximizes the distance to the closest occupied seat. If multiple seats yield the same maximum distance, the student chooses the seat with the lowest number. Initially, when the room is empty, the first student sits at seat 0.

The class should support two operations: seat(), which returns the chosen seat index according to the above rules, and leave(p), which marks seat p as empty. Implement this functionality efficiently to handle up to 10^4 seat and leave calls, ensuring distance maximization at every step.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

Input ["ExamRoom", "seat", "seat", "seat", "seat", "leave", "seat"] [[10], [], [], [], [], [4], []] Output [null, 0, 9, 4, 2, null, 5]

Explanation ExamRoom examRoom = new ExamRoom(10); examRoom.seat(); // return 0, no one is in the room, then the student sits at seat number 0. examRoom.seat(); // return 9, the student sits at the last seat number 9. examRoom.seat(); // return 4, the student sits at the last seat number 4. examRoom.seat(); // return 2, the student sits at the last seat number 2. examRoom.leave(4); examRoom.seat(); // return 5, the student sits at the last seat number 5.

Constraints

1 <= n <= 109
It is guaranteed that there is a student sitting at seat p.
At most 104 calls will be made to seat and leave.

Solution Approach

Track intervals using a max-heap

Maintain a max-heap of empty intervals, prioritized by the maximum possible distance a new student can achieve within the interval. When seating a student, pop the largest interval, choose the seat in the middle (or at an end if at boundaries), and split the interval into two new intervals pushed back into the heap.

Handle leaving efficiently

When a student leaves a seat, merge adjacent empty intervals into a single interval to restore the heap structure. Update the heap with the merged interval so future seat() calls still maximize distance correctly. Use a map or set to quickly locate neighboring intervals.

Optimize with ordered sets

Optionally, use an ordered set to maintain occupied seats in sorted order. This allows O(log n) queries to find the nearest occupied neighbors for any candidate seat, enabling efficient computation of distances without scanning the entire row.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Using a heap or ordered set, each seat() or leave() operation takes O(log k) time, where k is the current number of empty intervals. Space complexity is O(k) to store intervals or occupied seat positions.

What Interviewers Usually Probe

Check if your implementation updates intervals correctly after each seat and leave operation.
Consider how your heap or ordered set handles boundary seats and tie-breaking rules.
Ensure time complexity is efficient for up to 10^4 operations with large n.

Common Pitfalls or Variants

Common pitfalls

Failing to correctly merge intervals after a leave() call, leading to incorrect distance calculations.
Choosing the wrong seat when multiple positions yield the same maximum distance.
Scanning the entire seat row instead of using a heap or ordered set, causing timeouts for large n.

Follow-up variants

Implement Exam Room in a circular seating arrangement where the first and last seats are adjacent.
Allow multiple students to enter simultaneously and assign them to maximize distance collectively.
Track the k farthest empty seats instead of just the maximum distance seat for alternative seat selection strategies.

FAQ

What is the main strategy to implement Exam Room efficiently?

Use a max-heap to track empty intervals, always selecting the interval offering the maximum distance to the nearest student, and update intervals after seat() and leave() operations.

Can ordered sets replace heaps in Exam Room?

Yes, an ordered set of occupied seats can efficiently compute nearest neighbors, but it requires careful handling of seat insertion and removal to maintain distance correctness.

How do I handle tie-breaking when multiple seats have the same maximum distance?

Always choose the seat with the lowest index when distances are equal, as specified in the problem constraints.

What is the time complexity per operation in this design plus heap approach?

Each seat() or leave() operation takes O(log k) time, where k is the number of current empty intervals, ensuring fast execution for up to 10^4 operations.

Why does GhostInterview emphasize heap usage for Exam Room?

Heap structures efficiently maintain and retrieve the interval with the largest available distance, which is the core requirement for the Exam Room pattern.

terminal

Solution

Solution 1: Ordered Set + Hash Table

Considering that each time we call $\text{seat}()$, we need to find the seat with the maximum distance, we can use an ordered set to store seat intervals. Each element of the ordered set is a tuple $(l, r)$, indicating that the seats between $l$ and $r$ (excluding $l$ and $r$) can be occupied by a student. Initially, the ordered set contains only one element $(-1, n)$, indicating that the seats between $(-1, n)$ can be occupied by a student.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

class ExamRoom:
    def __init__(self, n: int):
        def dist(x):
            l, r = x
            return r - l - 1 if l == -1 or r == n else (r - l) >> 1

        self.n = n
        self.ts = SortedList(key=lambda x: (-dist(x), x[0]))
        self.left = {}
        self.right = {}
        self.add((-1, n))

    def seat(self) -> int:
        s = self.ts[0]
        p = (s[0] + s[1]) >> 1
        if s[0] == -1:
            p = 0
        elif s[1] == self.n:
            p = self.n - 1
        self.delete(s)
        self.add((s[0], p))
        self.add((p, s[1]))
        return p

    def leave(self, p: int) -> None:
        l, r = self.left[p], self.right[p]
        self.delete((l, p))
        self.delete((p, r))
        self.add((l, r))

    def add(self, s):
        self.ts.add(s)
        self.left[s[1]] = s[0]
        self.right[s[0]] = s[1]

    def delete(self, s):
        self.ts.remove(s)
        self.left.pop(s[1])
        self.right.pop(s[0])


# Your ExamRoom object will be instantiated and called as such:
# obj = ExamRoom(n)
# param_1 = obj.seat()
# obj.leave(p)

Continue Practicing

#1825 finding mk average #895 maximum frequency stack #1912 design movie rental system