这个题解使用了优先队列（最大堆）来快速找到最优的座位。首先，每个区间（即连续的空座位）被标记为一个三元组 [-priority, first, last]，其中 priority 是该区间的优先级，first 和 last 分别是区间的起始和结束座位。如果区间是开头或结尾的座位，优先级就是区间长度；否则，优先级是区间长度除以二的商。这样设计是为了优先坐在最中间的位置，以最大化与最近的人的距离。当座位被选取时，相关区间会被拆分并重新加入堆中，如果座位 p 被释放，相邻的空座位区间会合并并更新。
时间复杂度: O(log n)
空间复杂度: O(n)
from heapq import heappop, heappush
class ExamRoom(object):
def __init__(self, N):
self.N = N # 总座位数
self.heap = [] # 用于维护所有区间的最大堆
self.avail_first = {} # 存储以区间起点为键的区间映射
self.avail_last = {} # 存储以区间终点为键的区间映射
self.put_segment(0, self.N - 1) # 初始化，一开始整个区间都是空的
def put_segment(self, first, last):
if first == 0 or last == self.N - 1:
priority = last - first # 如果区间是边界，则取整个区间长度作为优先级
else:
priority = (last - first) // 2 # 否则取中间位置为优先级
segment = [-priority, first, last, True] # 创建区间，负号确保优先队列为最大堆
self.avail_first[first] = segment # 记录区间起点
self.avail_last[last] = segment # 记录区间终点
heappush(self.heap, segment) # 将区间推入堆中
def seat(self):
while True:
_, first, last, is_valid = heappop(self.heap) # 取出优先级最高的区间
if is_valid:
del self.avail_first[first] # 删除旧的映射
del self.avail_last[last] # 删除旧的映射
break # 找到有效区间，跳出循环
if first == 0:
ret = 0 # 选择第一个座位
if first != last:
self.put_segment(first + 1, last) # 更新区间
elif last == self.N - 1:
ret = last # 选择最后一个座位
if first != last:
self.put_segment(first, last - 1) # 更新区间
else:
ret = first + (last - first) // 2 # 选择中间座位
if ret > first:
self.put_segment(first, ret - 1) # 更新区间
if ret < last:
self.put_segment(ret + 1, last) # 更新区间
return ret # 返回选定的座位
def leave(self, p):
first = p # 开始点是 p
last = p # 结束点也是 p
left = p - 1 # 检查左邻座位
right = p + 1 # 检查右邻座位
if left >= 0 and left in self.avail_last:
segment_left = self.avail_last.pop(left) # 获取并删除左边的区间
segment_left[3] = False # 标记为无效
first = segment_left[1] # 扩展合并区间的起点
if right < self.N and right in self.avail_first:
segment_right = self.avail_first.pop(right) # 获取并删除右边的区间
segment_right[3] = False # 标记为无效
last = segment_right[2] # 扩展合并区间的终点
self.put_segment(first, last) # 合并区间并重新放入堆中