LC.855 ｜ 考场就座 ｜ 有序集合 ｜ set的应用

输入：

• 构造：ExamRoom(int n)，座位编号为[0, n-1]
• 操作：
  • seat()：安排下一位学生入座
  • leave(int p)：座位p的学生离开（保证p上有人）

要求：

• seat()必须选择离最近的人最远的位置；
• 若有多个满足条件，选编号最小的座位。

输出：

• seat()返回座位编号；leave()无返回。

思路：

用一个有序集合set<int> students维护当前已坐下的座位编号（自动有序）。

seat() 怎么找最优位置？

最优位置只可能出现在三类“空段”里：

1. 头部空段：从0到第一个已坐位置first

• 如果坐0，到最近人的距离就是first - 0 = first
• 所以头部候选距离dist = first，候选座位bestSeat = 0

2. 中间空段：两个相邻已坐座位prev和s之间

• 最优就是坐在中点（向下取整），距离为(s - prev) / 2
• 遍历students，对每一对相邻座位计算d = (s - prev) / 2
• 若d > dist，更新bestSeat = prev + d

3. 尾部空段：最后一个已坐位置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);}};