05 August 2008
在考场里，一排有 N 个座位，分别编号为 0, 1, 2, …, N-1 。
当学生进入考场后，他必须坐在能够使他与离他最近的人之间的距离达到最大化的座位上。如果有多个这样的座位，他会坐在编号最小的座位上。(另外，如果考场里没有人，那么学生就坐在 0 号座位上。)
返回 ExamRoom(int N) 类，它有两个公开的函数：其中，函数 ExamRoom.seat() 会返回一个 int （整型数据），代表学生坐的位置；函数 ExamRoom.leave(int p) 代表坐在座位 p 上的学生现在离开了考场。每次调用 ExamRoom.leave(p) 时都保证有学生坐在座位 p 上。
1
2
3
4
5
6
7
8
9
10
11
输入：["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 号座位上。
维护有序的座位编号
我们可以用有序集合（Java 中 TreeSet，C++ 中的 set）存储目前有学生的座位编号。当我们要调用 leave(p) 函数时，只需要把有序集合中的 p 移除即可。当要调用 seat() 函数时，遍历这个有序集合，对于相邻的两个座位 i 和 j，如果选择在这两个座位之间入座，那么最近的距离 d 为 (j - i) / 2，选择的座位为 i + d。除此之外，还需要考虑坐在最左侧 0 和最右侧 N - 1 的情况。
时间复杂度：seat() 函数的时间复杂度为 O(P)，其中 PP 是当前入座学生的数目。每次调用 seat() 函数都需要遍历整个有序集合。leave() 函数的时间复杂度为 O(P)（Python 代码中）或者 O(logP)（Java 代码中）。
空间复杂度：O(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
class ExamRoom {
int N;
TreeSet<Integer> students;
public ExamRoom(int N) {
this.N = N;
students = new TreeSet();
}
public int seat() {
//Let's determine student, the position of the next
//student to sit down.
int student = 0;
if (students.size() > 0) {
//Tenatively, distance is the distance to the closest student,
//which is achieved by sitting in the position 'student'.
//We start by considering the left-most seat.
int distance = students.first();
Integer prev = null;
for (Integer stu: students) {
if (prev != null) {
//For each pair of adjacent students in positions (prev, stu),
//d is the distance to the closest student;
//achieved at position prev + d.
int d = (stu - prev) / 2;
if (d > distance) {
distance = d;
student = prev + d;
}
}
prev = stu;
}
//Considering the right-most seat.
if (N - 1 - students.last() > distance)
student = N - 1;
}
//Add the student to our sorted TreeSet of positions.
students.add(student);
return student;
}
public void leave(int p) {
students.remove(p);
}
}
/**
* Your ExamRoom object will be instantiated and called as such:
* ExamRoom obj = new ExamRoom(n);
* int param_1 = obj.seat();
* obj.leave(p);
*/