Medium
题目描述
在一个有 n 个座位的考试房间中，座位按顺序编号为 0 到 n - 1。
当一个学生进入房间时，他必须坐在能够使与最近的人的距离最大化的座位上。如果有多个这样的座位，他要坐在编号最小的座位上。如果房间里没有人，那么学生就坐在 0 号座位上。
设计一个模拟上述考试房间的类。
实现 ExamRoom 类：
ExamRoom(int n)用座位数n初始化考试房间对象。int seat()返回下一个学生将要坐的座位的标号。void leave(int p)指示坐在座位p上的学生将离开房间。题目保证座位p上会有一个学生。
示例 1：
输入：
["ExamRoom", "seat", "seat", "seat", "seat", "leave", "seat"]
[[10], [], [], [], [], [4], []]
输出：
[null, 0, 9, 4, 2, null, 5]
解释：
ExamRoom examRoom = new ExamRoom(10);
examRoom.seat(); // 返回 0，房间里没有人，学生坐在 0 号座位。
examRoom.seat(); // 返回 9，学生坐在最后一个座位 9 号。
examRoom.seat(); // 返回 4，学生坐在座位 4 号。
examRoom.seat(); // 返回 2，学生坐在座位 2 号。
examRoom.leave(4);
examRoom.seat(); // 返回 5，学生坐在座位 5 号。
提示：
1 <= n <= 10^9- 题目保证座位
p上有学生。 - 最多会对
seat和leave进行10^4次调用。
解题思路
解题思路
这道题要求我们设计一个考试房间，学生入座时要选择距离最近的人最远的位置。
核心策略：
- 维护已占座位：使用有序集合（如 TreeSet）来维护当前已被占用的座位编号
- 找最佳座位：对于每次
seat()调用，遍历相邻的已占座位之间的间隔，找到能提供最大距离的位置 - 边界处理：特别处理房间两端（0号座位前和n-1号座位后）的情况
算法流程：
seat()：如果房间为空，返回0；否则计算所有可能位置的最小距离，选择最小距离最大的位置leave(p)：从已占座位集合中移除座位p
关键点：
- 对于两个相邻座位
a和b，中间最佳位置是(a+b)/2，此时距离为(b-a)/2 - 对于房间两端，0号位置的距离是到第一个人的距离，最后位置的距离是到最后一个人的距离
- 当距离相等时，选择编号较小的座位
时间复杂度方面，每次 seat() 需要 O(P) 时间（P为已占座位数），leave() 需要 O(log P) 时间。
代码实现
class ExamRoom {
private:
int n;
set<int> seated;
public:
ExamRoom(int n) : n(n) {}
int seat() {
if (seated.empty()) {
seated.insert(0);
return 0;
}
int maxDist = 0;
int bestSeat = 0;
// Check seat 0
int firstSeat = *seated.begin();
if (firstSeat > 0) {
maxDist = firstSeat;
bestSeat = 0;
}
// Check seats between occupied seats
auto it = seated.begin();
auto next = it;
++next;
while (next != seated.end()) {
int left = *it;
int right = *next;
int dist = (right - left) / 2;
if (dist > maxDist) {
maxDist = dist;
bestSeat = left + dist;
}
++it;
++next;
}
// Check last seat
int lastSeat = *seated.rbegin();
if (lastSeat < n - 1) {
int dist = n - 1 - lastSeat;
if (dist > maxDist) {
maxDist = dist;
bestSeat = n - 1;
}
}
seated.insert(bestSeat);
return bestSeat;
}
void leave(int p) {
seated.erase(p);
}
};
class ExamRoom:
def __init__(self, n: int):
self.n = n
self.seated = set()
def seat(self) -> int:
if not self.seated:
self.seated.add(0)
return 0
seated_list = sorted(self.seated)
max_dist = 0
best_seat = 0
# Check seat 0
if seated_list[0] > 0:
max_dist = seated_list[0]
best_seat = 0
# Check seats between occupied seats
for i in range(len(seated_list) - 1):
left = seated_list[i]
right = seated_list[i + 1]
dist = (right - left) // 2
if dist > max_dist:
max_dist = dist
best_seat = left + dist
# Check last seat
if seated_list[-1] < self.n - 1:
dist = self.n - 1 - seated_list[-1]
if dist > max_dist:
max_dist = dist
best_seat = self.n - 1
self.seated.add(best_seat)
return best_seat
def leave(self, p: int) -> None:
self.seated.remove(p)
public class ExamRoom {
private int n;
private SortedSet<int> seated;
public ExamRoom(int n) {
this.n = n;
this.seated = new SortedSet<int>();
}
public int Seat() {
if (seated.Count == 0) {
seated.Add(0);
return 0;
}
var seatedList = seated.ToList();
int maxDist = 0;
int bestSeat = 0;
// Check seat 0
if (seatedList[0] > 0) {
maxDist = seatedList[0];
bestSeat = 0;
}
// Check seats between occupied seats
for (int i = 0; i < seatedList.Count - 1; i++) {
int left = seatedList[i];
int right = seatedList[i + 1];
int dist = (right - left) / 2;
if (dist > maxDist) {
maxDist = dist;
bestSeat = left + dist;
}
}
// Check last seat
if (seatedList[seatedList.Count - 1] < n - 1) {
int dist = n - 1 - seatedList[seatedList.Count - 1];
if (dist > maxDist) {
maxDist = dist;
bestSeat = n - 1;
}
}
seated.Add(bestSeat);
return bestSeat;
}
public void Leave(int p) {
seated.Remove(p);
}
}
var ExamRoom = function(n) {
this.n = n;
this.seats = new Set();
};
ExamRoom.prototype.seat = function() {
if (this.seats.size === 0) {
this.seats.add(0);
return 0;
}
let sortedSeats = Array.from(this.seats).sort((a, b) => a - b);
let maxDist = 0;
let bestSeat = 0;
// Check seat 0
if (!this.seats.has(0)) {
maxDist = sortedSeats[0];
bestSeat = 0;
}
// Check between seats
for (let i = 0; i < sortedSeats.length - 1; i++) {
let left = sortedSeats[i];
let right = sortedSeats[i + 1];
let mid = Math.floor((left + right) / 2);
let dist = Math.min(mid - left, right - mid);
if (dist > maxDist) {
maxDist = dist;
bestSeat = mid;
}
}
// Check last seat
if (!this.seats.has(this.n - 1)) {
let dist = this.n - 1 - sortedSeats[sortedSeats.length - 1];
if (dist > maxDist) {
bestSeat = this.n - 1;
}
}
this.seats.add(bestSeat);
return bestSeat;
};
ExamRoom.prototype.leave = function(p) {
this.seats.delete(p);
};
复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 构造函数 | O(1) | O(1) |
| seat() | O(P) | O(P) |
| leave() | O(log P) | O(P) |
其中 P 表示当前已占用的座位数量。seat() 操作需要遍历所有已占用座位来寻找最佳位置，leave() 操作在有序集合中删除元素。空间复杂度主要用于存储已占用的座位。