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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
| class ExamRoom {
private Map<Integer, int[]> endMap;
private Map<Integer, int[]> startMap;
private TreeSet<int[]> intervals;
private int N;
public ExamRoom(int n) {
endMap = new HashMap<>();
startMap = new HashMap<>();
intervals = new TreeSet<>((a, b) -> {
int distanceA = distance(a);
int distanceB = distance(b);
if (distanceA != distanceB) {
return distanceA - distanceB;
}
return b[0] - a[0];
});
N = n;
intervals.add(new int[] { -1, N });
}
public int seat() {
Map<Integer, int[]> sM = this.startMap;
Map<Integer, int[]> eM = this.endMap;
TreeSet<int[]> inter = this.intervals;
int[] longestInterval = intervals.last();
int ans = -1;
if (longestInterval[0] == -1) {
ans = 0;
} else if (longestInterval[1] == N) {
ans = N - 1;
} else {
ans = (longestInterval[1] + longestInterval[0]) / 2;
}
removeInterval(longestInterval);
addInterval(new int[] { longestInterval[0], ans });
addInterval(new int[] { ans, longestInterval[1] });
return ans;
}
public void leave(int p) {
int[] leftInterval = endMap.get(p);
int[] rightInterval = startMap.get(p);
removeInterval(leftInterval);
removeInterval(rightInterval);
addInterval(new int[] { leftInterval[0], rightInterval[1] });
}
private void addInterval(int[] interval) {
startMap.put(interval[0], interval);
endMap.put(interval[1], interval);
intervals.add(interval);
}
private void removeInterval(int[] interval) {
startMap.remove(interval[0]);
endMap.remove(interval[1]);
intervals.remove(interval);
}
private int distance(int[] interval) {
if (interval[0] == -1) {
return interval[1];
}
if (interval[1] == N) {
return N - 1 - interval[0];
}
return (interval[1] - interval[0]) / 2;
}
private void print() {
System.out.println(startMap);
System.out.println(endMap);
System.out.println(intervals);
}
}
|
这道题很有意思, 属于那种我们边想边有问题, 然后怎么解决? 解决完后又有问题, 直到最后没问题了, 写的方法也就出来了. 开始我们需要知道哪个interval最长, 但是有个问题, 那就是最长的不一定满足题意.比如一个interval长度为3, 但是靠前. 一个interval长度为4靠后, 那么在这两个interval的中间安放一个人, 距离interval左端的距离都是2, 但是3更靠前, 因此需要选3. 这样的话, 本质就是谁距离左端最近. 我们于是要计算距离左端的距离而非interval的长度.
其次当我们插入一个人后, 之前的interval被一分为二. 我们需要把这个原来的较长的interval移除然后添加两个新的子intervals. 这没问题, 我们是知道原interval的以及要插入的点.
最后是我们如果移除一个人, 那么会将两个interval合并. 这要怎么做? 我们可以记录每个interval的start和end, 分别在map中. 也就是这两个map如果给它们一个start或者end, 它们就能告诉我们对应的interval是谁. 每个interval的start和别人肯定都不同, end也是一样的.
至此我们的逻辑就差不多了. 一个是需要能够告诉我们在available的intervals中候选的位置距离人最远, 如果有多个, 那就比较哪个interval靠前. 很自然的我们就想到使用TreeSet. 为什么不用PQ? 因为我们需要有时候移除非顶端的element. 然后用两个map来存所有intervals的start和end.
我们需要注意的是一开始我们要把人放到第0个位置, 下一个人放到最后一个位置. 这两个算是edge case. 我们如何解决这个问题呢? 就是按照我们的逻辑我们从set中找出一个最长的interval(这里的长指的是距离这个interval最左端的最远), 然后取中点, 之后把旧的interval移走, 新的两个interval加进来. 一个聪明的做法就是加入一个{-1, N}的pair. 然后如果出来的interval左端是-1, 那我们直接放到0的位置, 此时不能取该interval的中点, 最左端是距离其他人最远的地方. 如果interval出来右端是N, 那一定要放在N - 1处. 然后后面就移除旧interval添加新的两个interval就行了.
你可能会说, 有可能添加start和hend挨着的interval. 确实会出现这种情况, 但是由于我们是TreeSet, 这样的intervals肯定都在最后面.由于题目说seat的时候肯定有位置, 那我们就不会取到这些length是0的intervals了.
中间遇到了一个bug, 后来发现35行需要先remove再add, 如果先add, 再remove, 那会把add好的东西给移除走. add中会覆盖longestInterval两端在不同map中对应的interval, 然后我们再remove, 那之前add的东西就被remove走了. 这需要注意.
时间复杂度: seat是O(logn) leave是O(1)
空间复杂度: O(n) 因为可能每个点即是start又是end. 在map中和set中存满了.
