LeetCode 855 - Exam Room

This problem requires designing a simulation for an exam room seating arrangement. We have n seats in a single row, labeled from 0 to n - 1. Students enter one by one, and each student chooses a seat such that the distance to the closest occupied seat is maximized.

leetcodemediumdesignheap-(priority-queue)ordered-set

LeetCode Problem 855

Difficulty: 🟡 Medium
Topics: Design, Heap (Priority Queue), Ordered Set

Solution

Problem Understanding

This problem requires designing a simulation for an exam room seating arrangement. We have n seats in a single row, labeled from 0 to n - 1. Students enter one by one, and each student chooses a seat such that the distance to the closest occupied seat is maximized. If there are multiple seats that achieve the same maximum distance, the student chooses the seat with the smallest index. If the room is empty, the first student sits at seat 0.

The input represents a series of operations on the ExamRoom class: initialization with the number of seats, seating a student, or removing a student from a specific seat. The output is the seat numbers returned by seat() calls or null for operations that do not produce a return value.

The constraints are significant. n can be as large as 10^9, meaning we cannot store all seats explicitly in memory. Up to 10^4 operations will be performed, so the solution must efficiently find the optimal seat and handle removals. The problem guarantees that leave(p) will only be called for seats that are currently occupied, which simplifies error handling.

Edge cases include an empty room, a room with one student, students sitting at the ends of the row, and consecutive leaves that may merge intervals of free seats. Handling the largest possible seat index efficiently without iterating through all positions is crucial.

Approaches

A brute-force approach would maintain a list or array of occupied seats. For each seat() operation, we would iterate through all free positions, calculate the distance to the nearest occupied seat, and choose the one maximizing that distance. While correct, this approach is too slow for large n because iterating over potentially billions of seats is infeasible.

The key insight for an optimal solution is that we only need to track intervals of empty seats instead of individual seats. Each interval can be represented by its starting and ending occupied positions (or boundaries for the edges). The seat chosen is always at the midpoint of the largest interval (or at the boundary if it is the first or last seat). Using a priority queue (max-heap) to store intervals by their potential maximum distance allows seat() to be efficient. We also need a data structure (like a set or map) to efficiently merge intervals when a student leaves.

By focusing on intervals rather than individual seats, we reduce the problem to efficiently maintaining these intervals and finding the largest one.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) per seat O(n) Iterate through all seats to find the maximum distance. Feasible only for small n.
Optimal O(log k) per seat/leave O(k) Maintain intervals in a priority queue, where k is the number of occupied seats. Efficient for large n and many operations.

Algorithm Walkthrough

  1. Initialize an empty room with n seats. Maintain a max-heap of intervals, initially containing the interval [0, n - 1].
  2. When a student enters (seat()):

a. Pop the interval with the maximum potential distance from the heap. Calculate the seat to occupy: if the interval includes the first or last seat, choose the boundary; otherwise, choose the midpoint.

b. Split the interval into two smaller intervals, excluding the chosen seat, and push them back into the heap.

c. Mark the seat as occupied. 3. When a student leaves (leave(p)):

a. Identify intervals adjacent to seat p that need merging. Remove old intervals from the heap.

b. Create a new merged interval that includes the freed seat and push it back into the heap. 4. Use a comparison function for the heap that prioritizes intervals by distance first, then by the lower seat index if distances are equal.

Why it works: The algorithm maintains the invariant that the heap always contains the largest available intervals. Seating at the midpoint of the largest interval guarantees the maximum distance from other students. When merging intervals, the heap is updated, so the next seat will always be optimal.

Python Solution

import heapq

class ExamRoom:
    def __init__(self, n: int):
        self.n = n
        self.heap = []
        self.occupied = set()
        # store intervals as (-distance, start, end)
        heapq.heappush(self.heap, (-self.distance(0, n - 1), 0, n - 1))

    def distance(self, start, end):
        if start == 0 or end == self.n - 1:
            return end - start
        return (end - start) // 2

    def seat(self) -> int:
        while True:
            neg_dist, start, end = heapq.heappop(self.heap)
            if start not in self.occupied or end not in self.occupied or start == 0 or end == self.n - 1:
                break

        if start == 0:
            seat = 0
        elif end == self.n - 1:
            seat = self.n - 1
        else:
            seat = (start + end) // 2

        self.occupied.add(seat)

        if seat > start:
            heapq.heappush(self.heap, (-self.distance(start, seat - 1), start, seat - 1))
        if seat < end:
            heapq.heappush(self.heap, (-self.distance(seat + 1, end), seat + 1, end))

        return seat

    def leave(self, p: int) -> None:
        self.occupied.remove(p)
        left = p - 1
        right = p + 1
        start, end = p, p

        while left in self.occupied:
            left -= 1
        if left >= 0:
            start = left + 1

        while right in self.occupied:
            right += 1
        if right < self.n:
            end = right - 1

        heapq.heappush(self.heap, (-self.distance(start, end), start, end))

The Python solution uses a max-heap to keep track of intervals sorted by the maximum distance a student can achieve. It efficiently pops the largest interval, chooses the optimal seat, and pushes the resulting sub-intervals back into the heap. The occupied set allows constant-time checks for interval boundaries.

Go Solution

package main

import (
    "container/heap"
)

type Interval struct {
    start, end int
    dist       int
}

type MaxHeap []Interval

func (h MaxHeap) Len() int { return len(h) }
func (h MaxHeap) Less(i, j int) bool {
    if h[i].dist == h[j].dist {
        return h[i].start < h[j].start
    }
    return h[i].dist > h[j].dist
}
func (h MaxHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x any)  { *h = append(*h, x.(Interval)) }
func (h *MaxHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

type ExamRoom struct {
    n        int
    heap     MaxHeap
    occupied map[int]bool
}

func Constructor(n int) ExamRoom {
    h := MaxHeap{{0, n - 1, n - 1}}
    return ExamRoom{n, h, make(map[int]bool)}
}

func distance(n, start, end int) int {
    if start == 0 || end == n-1 {
        return end - start
    }
    return (end - start) / 2
}

func (this *ExamRoom) Seat() int {
    for {
        interval := heap.Pop(&this.heap).(Interval)
        if !this.occupied[interval.start] || !this.occupied[interval.end] || interval.start == 0 || interval.end == this.n-1 {
            var seat int
            if interval.start == 0 {
                seat = 0
            } else if interval.end == this.n-1 {
                seat = this.n - 1
            } else {
                seat = (interval.start + interval.end) / 2
            }
            this.occupied[seat] = true
            if seat > interval.start {
                heap.Push(&this.heap, Interval{interval.start, seat - 1, distance(this.n, interval.start, seat-1)})
            }
            if seat < interval.end {
                heap.Push(&this.heap, Interval{seat + 1, interval.end, distance(this.n, seat+1, interval.end)})
            }
            return seat
        }
    }
}

func (this *ExamRoom) Leave(p int) {
    delete(this.occupied, p)
    left, right := p, p
    for this.occupied[left-1] {
        left--
    }
    for this.occupied[right+1] {
        right++
    }
    heap.Push(&this.heap, Interval{left, right, distance(this.n, left, right)})
}

The Go implementation mirrors the Python version but uses a container/heap for the priority queue. Intervals are stored in a struct, and the heap comparison prioritizes larger distances, breaking ties with lower indices. The occupied map allows efficient membership checks.

Worked Examples

For the example:

examRoom = ExamRoom(10)
examRoom.seat() ->