LC.855 ｜ 考场就座 ｜ 有序集合 ｜ set的应用
输入：
- 构造：
ExamRoom(int n)，座位编号为[0, n-1] - 操作：
seat()：安排下一位学生入座leave(int p)：座位p的学生离开（保证p上有人）
要求：
seat()必须选择离最近的人最远的位置；- 若有多个满足条件，选编号最小的座位。
输出：
seat()返回座位编号；leave()无返回。
思路：
用一个有序集合set<int> students维护当前已坐下的座位编号（自动有序）。
seat() 怎么找最优位置？
最优位置只可能出现在三类“空段”里：
- 头部空段：从
0到第一个已坐位置first
- 如果坐
0，到最近人的距离就是first - 0 = first - 所以头部候选距离
dist = first，候选座位bestSeat = 0
- 中间空段：两个相邻已坐座位
prev和s之间
- 最优就是坐在中点（向下取整），距离为
(s - prev) / 2 - 遍历
students，对每一对相邻座位计算d = (s - prev) / 2 - 若
d > dist，更新bestSeat = prev + d
- 尾部空段：最后一个已坐位置
last到n-1
- 如果坐
n-1，距离就是(n-1) - last - 若
tailDist > dist，更新bestSeat = n-1
最后把bestSeat插入集合并返回。
leave()
直接students.erase(p)即可。
复杂度：
- 时间复杂度：
seat()：O(M) 扫描当前已坐人数M（set 遍历） + 插入 O(log M)leave()：O(log M)
- 空间复杂度：O(M)
classExamRoom{private:intN;set<int>students;public:ExamRoom(intn){N=n;}intseat(){if(students.empty()){students.insert(0);return0;}intdist=*students.begin();// 头部空段距离intbestSeat=0;intprev=-1;for(ints:students){if(prev!=-1){intd=(s-prev)/2;if(d>dist){dist=d;bestSeat=prev+d;}}prev=s;}inttailDist=(N-1)-*students.rbegin();if(tailDist>dist){bestSeat=N-1;}students.insert(bestSeat);returnbestSeat;}voidleave(intp){students.erase(p);}};