LeetCode 题解工作台
考场就座
在考场里，有 n 个座位排成一行，编号为 0 到 n - 1 。 当学生进入考场后，他必须坐在离最近的人最远的座位上。如果有多个这样的座位，他会坐在编号最小的座位上。(另外，如果考场里没有人，那么学生就坐在 0 号座位上。) 设计一个模拟所述考场的类。 实现 ExamRoom 类： ExamRoom…
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 堆
答案摘要
考虑到每次 时都需要找到最大距离的座位，我们可以使用有序集合来保存座位区间。有序集合的每个元素为一个二元组 $(l, r)$，表示 和 之间（不包括 和 ）的座位可以坐学生。初始时有序集合中只有一个元素 $(-1, n)$，表示 $(-1, n)$ 之间的座位可以坐学生。 另外，我们使用两个哈希表 和 来维护每个有学生的座位的左右邻居学生，方便我们在 时合并两个座位区间。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 堆 题型思路
题目描述
在考场里，有 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 <= 109- 保证有学生正坐在座位
p上。 seat和leave最多被调用104次。
解题思路
方法一：有序集合 + 哈希表
考虑到每次 时都需要找到最大距离的座位，我们可以使用有序集合来保存座位区间。有序集合的每个元素为一个二元组 ，表示 和 之间（不包括 和 ）的座位可以坐学生。初始时有序集合中只有一个元素 ，表示 之间的座位可以坐学生。
另外，我们使用两个哈希表 和 来维护每个有学生的座位的左右邻居学生，方便我们在 时合并两个座位区间。
时间复杂度 ，空间复杂度 。其中 为考场的座位数。
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)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Check if your implementation updates intervals correctly after each seat and leave operation.
- question_mark
Consider how your heap or ordered set handles boundary seats and tie-breaking rules.
- question_mark
Ensure time complexity is efficient for up to 10^4 operations with large n.
常见陷阱
外企场景- error
Failing to correctly merge intervals after a leave() call, leading to incorrect distance calculations.
- error
Choosing the wrong seat when multiple positions yield the same maximum distance.
- error
Scanning the entire seat row instead of using a heap or ordered set, causing timeouts for large n.
进阶变体
外企场景- arrow_right_alt
Implement Exam Room in a circular seating arrangement where the first and last seats are adjacent.
- arrow_right_alt
Allow multiple students to enter simultaneously and assign them to maximize distance collectively.
- arrow_right_alt
Track the k farthest empty seats instead of just the maximum distance seat for alternative seat selection strategies.