Exam Room
Problem
Seats are 0..n-1. seat() returns the seat that maximizes distance to the nearest occupied seat (preferring lower indices on ties). leave(p) frees seat p.
n = 10; calls: seat(), seat(), seat(), seat(), leave(4), seat()[0, 9, 4, 2, 5]from sortedcontainers import SortedList
class ExamRoom:
def __init__(self, n):
self.n = n
self.seats = SortedList()
def seat(self):
if not self.seats:
self.seats.add(0); return 0
best, pos = self.seats[0], 0
for i in range(1, len(self.seats)):
d = (self.seats[i] - self.seats[i - 1]) // 2
if d > best: best, pos = d, self.seats[i - 1] + d
if self.n - 1 - self.seats[-1] > best:
pos = self.n - 1
self.seats.add(pos); return pos
def leave(self, p):
self.seats.remove(p)
class ExamRoom {
constructor(n) { this.n = n; this.seats = []; }
seat() {
if (this.seats.length === 0) { this.seats.push(0); return 0; }
let best = this.seats[0], pos = 0;
for (let i = 1; i < this.seats.length; i++) {
const d = (this.seats[i] - this.seats[i - 1]) >> 1;
if (d > best) { best = d; pos = this.seats[i - 1] + d; }
}
if (this.n - 1 - this.seats[this.seats.length - 1] > best) pos = this.n - 1;
const idx = this.seats.findIndex(s => s > pos);
if (idx === -1) this.seats.push(pos); else this.seats.splice(idx, 0, pos);
return pos;
}
leave(p) { this.seats.splice(this.seats.indexOf(p), 1); }
}
import java.util.*;
class ExamRoom {
int n; TreeSet<Integer> seats = new TreeSet<>();
public ExamRoom(int n) { this.n = n; }
public int seat() {
if (seats.isEmpty()) { seats.add(0); return 0; }
int best = seats.first(), pos = 0, prev = -1;
for (int s : seats) {
if (prev >= 0) {
int d = (s - prev) / 2;
if (d > best) { best = d; pos = prev + d; }
}
prev = s;
}
if (n - 1 - seats.last() > best) pos = n - 1;
seats.add(pos);
return pos;
}
public void leave(int p) { seats.remove(p); }
}
#include <bits/stdc++.h>
using namespace std;
class ExamRoom {
public:
int n;
set<int> seats;
ExamRoom(int n_) : n(n_) {}
int seat() {
if (seats.empty()) { seats.insert(0); return 0; }
int best = *seats.begin(), pos = 0, prev = -1;
for (int s : seats) {
if (prev >= 0) {
int d = (s - prev) / 2;
if (d > best) { best = d; pos = prev + d; }
}
prev = s;
}
if (n - 1 - *seats.rbegin() > best) pos = n - 1;
seats.insert(pos);
return pos;
}
void leave(int p) { seats.erase(p); }
};
Explanation
Each student wants to sit as far as possible from anyone already seated. The idea is to keep the occupied seats in sorted order and, on every seat(), scan the gaps between neighbours to find the spot with the largest distance to its nearest person.
We store occupied seats in a sorted structure (a SortedList, TreeSet, or set). If the room is empty, the answer is always seat 0.
Otherwise we consider three kinds of positions. The left edge: distance from seat 0 to the first occupied seat. Each interior gap between two occupied seats a and b: the best seat is the midpoint, giving distance (b - a) // 2. And the right edge: distance from the last occupied seat to seat n-1. We track the position with the maximum distance, and because we scan left to right and only replace on a strictly larger gap, ties naturally favor the smaller index.
leave(p) simply removes p from the sorted set so future gap calculations reflect the freed seat.
Example with n = 10: the first sit takes 0, then 9 (far right edge), then 4 (midpoint of the big 0..9 gap), then 2. After leave(4), the gap from 2 to 9 reopens, so the next seat() picks 5 — giving the sequence [0, 9, 4, 2, 5].