Code Implementation

import bisect

class ExamRoom:
    def __init__(self, N):
        self.N = N
        self.seats = []

    def seat(self):
        if not self.seats:
            self.seats.append(0)
            return 0
        max_dist = self.seats[0]
        seat_idx = 0

        for i in range(1, len(self.seats)):
            prev = self.seats[i-1]
            curr = self.seats[i]
            dist = (curr - prev) // 2
            if dist > max_dist:
                max_dist = dist
                seat_idx = prev + dist

        if self.N - 1 - self.seats[-1] > max_dist:
            seat_idx = self.N - 1

        bisect.insort(self.seats, seat_idx)
        return seat_idx

    def leave(self, p):
        idx = bisect.bisect_left(self.seats, p)
        if idx < len(self.seats) and self.seats[idx] == p:
            self.seats.pop(idx)

#include <set>
class ExamRoom {
    int N;
    std::set<int> seats;
public:
    ExamRoom(int N): N(N) {}

    int seat() {
        if (seats.empty()) {
            seats.insert(0);
            return 0;
        }
        int dist = *seats.begin();
        int seat_idx = 0;
        int prev = -1;
        for (int s : seats) {
            if (prev != -1) {
                int d = (s - prev) / 2;
                if (d > dist) {
                    dist = d;
                    seat_idx = prev + d;
                }
            }
            prev = s;
        }
        if (N - 1 - *seats.rbegin() > dist) {
            seat_idx = N - 1;
        }
        seats.insert(seat_idx);
        return seat_idx;
    }

    void leave(int p) {
        seats.erase(p);
    }
};

import java.util.TreeSet;

class ExamRoom {
    private int N;
    private TreeSet<Integer> seats;

    public ExamRoom(int N) {
        this.N = N;
        this.seats = new TreeSet<>();
    }

    public int seat() {
        if (seats.size() == 0) {
            seats.add(0);
            return 0;
        }
        int prev = -1, seat_idx = 0, dist = seats.first();
        for (int s : seats) {
            if (prev != -1) {
                int d = (s - prev) / 2;
                if (d > dist) {
                    dist = d;
                    seat_idx = prev + d;
                }
            }
            prev = s;
        }
        if (N - 1 - seats.last() > dist) {
            seat_idx = N - 1;
        }
        seats.add(seat_idx);
        return seat_idx;
    }

    public void leave(int p) {
        seats.remove(p);
    }
}

class ExamRoom {
    constructor(N) {
        this.N = N;
        this.seats = [];
    }

    seat() {
        if (this.seats.length === 0) {
            this.seats.push(0);
            return 0;
        }
        this.seats.sort((a, b) => a - b);
        let maxDist = this.seats[0];
        let seatIdx = 0;
        for (let i = 1; i < this.seats.length; i++) {
            let prev = this.seats[i-1];
            let curr = this.seats[i];
            let d = Math.floor((curr - prev) / 2);
            if (d > maxDist) {
                maxDist = d;
                seatIdx = prev + d;
            }
        }
        if (this.N - 1 - this.seats[this.seats.length - 1] > maxDist) {
            seatIdx = this.N - 1;
        }
        let idx = this.seats.findIndex(x => x > seatIdx);
        if (idx === -1) this.seats.push(seatIdx);
        else this.seats.splice(idx, 0, seatIdx);
        return seatIdx;
    }

    leave(p) {
        let idx = this.seats.indexOf(p);
        if (idx !== -1) {
            this.seats.splice(idx, 1);
        }
    }
}

Problem Description

You are designing an Exam Room with N seats in a single row, numbered from 0 to N-1. When a student enters, they must choose a seat such that the distance to the closest occupied seat is maximized. If there are multiple seats with the same maximum distance, the student chooses the seat with the lowest number. You must support two operations:

• seat(): A student enters and takes a seat following the rule above. Returns the seat number.
• leave(p): The student in seat p leaves. It is guaranteed that seat p is currently occupied.

You need to implement a class that efficiently supports these operations for multiple calls, always maintaining the correct seat assignment and vacancy status.

Thought Process

At first glance, the problem seems to require checking all seats for every seat() operation, which would be inefficient. The key insight is to focus on the gaps between occupied seats, as new students will always want to sit as far as possible from others. For each operation, we want to quickly find the largest available gap and determine the optimal seat within that gap.

If we store the occupied seats in a sorted list or set, we can efficiently find the largest gap between any two occupied seats, as well as the edges (beginning and end of the row). This allows us to avoid checking every seat and instead only consider intervals between occupied seats.

We also need to efficiently insert and remove seats as students enter and leave, which suggests using a data structure that supports fast insertion, deletion, and neighbor queries.

Solution Approach

Let's break down the algorithm step by step:

1. Data Structure:
   • We use a sorted list (or set) to keep track of currently occupied seats. This allows us to efficiently find neighbors and insert or remove seats in O(log n) time.
2. Seating a Student (seat()):
   • If the room is empty, the student sits at seat 0.
   • Otherwise, we consider three types of intervals:
     • The interval before the first occupied seat (distance = first seat index).
     • The intervals between every pair of adjacent occupied seats (distance = half the gap between them).
     • The interval after the last occupied seat (distance = N - 1 - last seat index).
   • We select the interval with the maximum minimal distance. If there are ties, we select the seat with the lowest index.
   • We insert the new seat into our data structure.
3. Leaving a Seat (leave(p)):
   • Simply remove seat p from our data structure.
4. Why Sorted?
   • Since we need to find adjacent seats and maintain order, a sorted list or set is ideal.
5. Efficiency:
   • Each operation (seat, leave) is O(log n) due to insertion and deletion in the sorted data structure.

Example Walkthrough

Let's walk through an example with N = 10 and a sequence of operations:

• Initial state: No seats occupied.
• seat(): Room is empty, student takes seat 0. (seats = [0])
• seat(): Gaps: [0,9] (distance 9). Student takes seat 9. (seats = [0,9])
• seat(): Gaps: [0,9] split at 4 (distance 4). Student takes seat 4. (seats = [0,4,9])
• seat(): Gaps: [0,4] (distance 2), [4,9] (distance 2). Student takes seat 2. (seats = [0,2,4,9])
• leave(4): Remove seat 4. (seats = [0,2,9])
• seat(): Gaps: [2,9] (distance 3). Student takes seat 5. (seats = [0,2,5,9])

At each step, we only need to consider the largest gaps between occupied seats and the edges.

Time and Space Complexity

Brute-Force Approach:

• For each seat(), check every seat for the minimum distance to any other occupied seat. This is O(N^2) per operation, which is too slow for large N.

• We use a sorted data structure (like a TreeSet, set, or list with binary search) to maintain occupied seats.
• Each seat() and leave() operation involves:
  • Finding neighbors and inserting/removing in O(log n) time (where n is the number of occupied seats).
  • Scanning all intervals between occupied seats, which is O(n) per seat() (since we must check all pairs).
• So, each operation is O(n) time, and O(n) space overall.

Further Optimizations: For very high performance, a priority queue of intervals can be used to achieve O(log n) seat assignment, but the above approach is sufficient for most constraints.

Summary

The Exam Room problem is a great exercise in interval management and greedy algorithms. By keeping track of occupied seats in a sorted data structure, we can always find the largest available gap for a new student efficiently. The solution elegantly balances between simplicity and efficiency, making use of sorted collections and careful interval analysis to maintain the optimal seating arrangement after every operation.