友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
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 <= 109 -
在所有的测试样例中
ExamRoom.seat()和ExamRoom.leave()最多被调用10^4次。 -
保证在调用
ExamRoom.leave(p)时有学生正坐在座位p上。
思路分析
有序集合+优先队列：有序集合保存已选位置，优先队列保存下一个符合要求的位置。
| 延迟删除的技巧，还需要再琢磨一下。 |
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-08-09 22:10:35
*/
class ExamRoom {
int n;
TreeSet<Integer> seats;
PriorityQueue<int[]> queue;
public ExamRoom(int n) {
this.n = n;
this.seats = new TreeSet<>();
this.queue = new PriorityQueue<>((a, b) -> {
int d1 = a[1] - a[0], d2 = b[1] - b[0];
return d1 / 2 < d2 / 2 || (d1 / 2 == d2 / 2 && a[0] > b[0]) ? 1 : -1;
});
}
public int seat() {
if (seats.isEmpty()) {
seats.add(0);
return 0;
}
int left = seats.first(), right = n - 1 - seats.last();
while (seats.size() >= 2) {
int[] p = queue.peek();
// 不属于延迟删除的区间
if (seats.contains(p[0]) && seats.contains(p[1]) && seats.higher(p[0]) == p[1]) {
int d = p[1] - p[0];
if (d / 2 < right || d / 2 <= left) { // 最左或最右的座位更优
break;
}
queue.poll();
queue.offer(new int[]{p[0], p[0] + d / 2});
queue.offer(new int[]{p[0] + d / 2, p[1]});
seats.add(p[0] + d / 2);
return p[0] + d / 2;
}
queue.poll(); // leave 函数中延迟删除的区间在此时删除
}
if (right > left) { // 最右的位置更优
queue.offer(new int[]{seats.getLast(), n - 1});
seats.add(n - 1);
return n - 1;
} else {
queue.offer(new int[]{0, seats.getFirst()});
seats.add(0);
return 0;
}
}
public void leave(int p) {
if (p != seats.first() && p != seats.last()) {
int prev = seats.lower(p), next = seats.higher(p);
queue.offer(new int[]{prev, next});
}
seats.remove(p);
}
}