[LeetCode] 每日一题 855. 考场就座
题目链接
题目描述
在考场里，一排有 N 个座位，分别编号为 0, 1, 2, ..., N-1 。
当学生进入考场后，他必须坐在能够使他与离他最近的人之间的距离达到最大化的座位上。如果有多个这样的座位，他会坐在编号最小的座位上。(另外，如果考场里没有人，那么学生就坐在 0 号座位上。)
返回 ExamRoom(int N) 类，它有两个公开的函数：其中，函数 ExamRoom.seat() 会返回一个 int （整型数据），代表学生坐的位置；函数 ExamRoom.leave(int p) 代表坐在座位 p 上的学生现在离开了考场。每次调用 ExamRoom.leave(p) 时都保证有学生坐在座位 p 上。
示例输入
示例
输入：["ExamRoom","seat","seat","seat","seat","leave","seat"], [[10],[],[],[],[],[4],[]]
输出：[null,0,9,4,2,null,5]
解释：
ExamRoom(10) -> null
seat() -> 0，没有人在考场里，那么学生坐在 0 号座位上。
seat() -> 9，学生最后坐在 9 号座位上。
seat() -> 4，学生最后坐在 4 号座位上。
seat() -> 2，学生最后坐在 2 号座位上。
leave(4) -> null
seat() -> 5，学生最后坐在 5 号座位上。提示
1 <= N <= 10^9在所有的测试样例中
ExamRoom.seat()和ExamRoom.leave()最多被调用10^4次。保证在调用
ExamRoom.leave(p)时有学生正坐在座位p上。
题解
解题思路
本题要求设计一个 ExamRoom 类，支持以下操作：
seat()：找到一个使得与离该学生最近的其他学生距离最大化的座位。leave(p)：让座位p上的学生离开。
关键在于如何高效地找到可以让学生距离最大化的座位。为了实现这一点，可以采用以下策略：
使用有序集合
TreeSet：
使用TreeSet存储所有可能的座位区间(l, r)，按区间“可用距离”降序排列，若距离相同则按区间起点升序排列。起点为
l，终点为r，表示区间(l, r)之间是空的，可以坐学生。初始时，有唯一区间
(-1, N)，表示整排座位都空。
辅助哈希表：
使用两个哈希表left和right分别记录每个已坐座位的左右邻居，便于快速更新区间。核心操作：
seat()：从TreeSet中找到距离最大的区间(l, r)，然后根据情况选择座位：如果区间左端
l == -1，选择最左边的座位0。如果区间右端
r == N，选择最右边的座位N-1。否则，选择区间的中点。 更新区间信息，移除旧区间
(l, r)，插入两个新区间(l, p)和(p, r)。
leave(p)：查找座位p的左右邻居，将区间合并，更新TreeSet和哈希表。
代码实现
class ExamRoom {
// 用 TreeSet 存储区间，按区间“可用距离”降序排列，若距离相同按起点升序排列
private TreeSet<int[]> valid = new TreeSet<>((a, b) -> {
int d1 = calDistance(a), d2 = calDistance(b);
return d1 == d2 ? a[0] - b[0] : d2 - d1;
});
// left 和 right 分别记录每个座位左右邻居的座位号
private Map<Integer, Integer> left = new HashMap<>();
private Map<Integer, Integer> right = new HashMap<>();
private int n; // 考场座位总数
// 初始化考场
public ExamRoom(int n) {
this.n = n;
// 初始状态只有一个大区间 (-1, n)，表示所有座位为空
add(new int[] {-1, n});
}
// 安排座位
public int seat() {
// 获取距离最大的区间
int[] s = valid.first();
int p; // 学生坐的座位号
// 根据区间的位置选择座位
if (s[0] == -1) {
// 如果区间左端为 -1，选择最左边座位 0
p = 0;
} else if (s[1] == n) {
// 如果区间右端为 n，选择最右边座位 n-1
p = n - 1;
} else {
// 否则选择区间中点
p = (s[0] + s[1]) >> 1;
}
// 更新区间
del(s); // 删除旧区间
add(new int[] {s[0], p}); // 插入左半区间
add(new int[] {p, s[1]}); // 插入右半区间
return p; // 返回学生坐的位置
}
// 离开座位
public void leave(int p) {
// 获取座位 p 的左右邻居
int l = left.get(p), r = right.get(p);
// 删除 p 左右的两个区间
del(new int[] {l, p});
del(new int[] {p, r});
// 合并成一个新的区间
add(new int[] {l, r});
}
// 计算区间的最大可用距离
private int calDistance(int[] s) {
int l = s[0], r = s[1];
// 如果区间左端是 -1 或右端是 n，距离是 r - l - 1
if (l == -1 || r == n) return r - l - 1;
// 否则，返回中点到边界的距离
return (r - l) >> 1;
}
// 添加一个区间到 valid 中，并更新哈希表
private void add(int[] s) {
valid.add(s); // 将区间加入 TreeSet
left.put(s[1], s[0]); // 更新右端点的左邻居
right.put(s[0], s[1]); // 更新左端点的右邻居
}
// 从 valid 中删除一个区间，并更新哈希表
private void del(int[] s) {
valid.remove(s); // 从 TreeSet 删除区间
left.remove(s[1]); // 删除右端点的左邻居
right.remove(s[0]); // 删除左端点的右邻居
}
}
复杂度分析
seat()：查找最大距离的区间：
O(log k)，其中k是当前的区间数。插入两个新区间并更新哈希表：
O(log k)。总复杂度：
O(log k)。
leave(p)：删除两个旧区间：
O(log k)。插入一个新区间并更新哈希表：
O(log k)。总复杂度：
O(log k)。
空间复杂度：
使用了
TreeSet和两个HashMap，总的空间复杂度为O(N)。
总结
本题通过 TreeSet 维护座位区间，确保每次 seat() 和 leave() 操作都能在 O(log N) 的复杂度内完成，满足高效性要求。
代码的关键在于：
精确定义区间和距离的计算方法。
使用哈希表快速更新区间信息。
这种方法对于类似需要动态操作和区间管理的题目也有很好的借鉴意义。
希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。