Leetcode855：考场就座

题目描述：

在考场里，有 n 个座位排成一行，编号为 0 到 n - 1。

当学生进入考场后，他必须坐在离最近的人最远的座位上。如果有多个这样的座位，他会坐在编号最小的座位上。(另外，如果考场里没有人，那么学生就坐在 0 号座位上。)

设计一个模拟所述考场的类。

实现 ExamRoom 类：

• ExamRoom(int n) 用座位的数量 n 初始化考场对象。
• int seat() 返回下一个学生将会入座的座位编号。
• void leave(int p) 指定坐在座位 p 的学生将离开教室。保证座位 p 上会有一位学生。

代码思路：

类初始化

• __init__(self, n: int): 构造函数接收一个整数 n，表示考试室的总座位数。它创建了一个 SortedList 实例 self.sl 来存储已分配的座位号（这些座位号将保持有序），并保存了总座位数 self.n。

座位分配

• seat(self) -> int: 此方法用于分配一个新的座位号。
  • 空列表情况：若 self.sl 为空（即尚未分配任何座位），则分配座位号 0 并返回。
  • 非空列表情况：若 self.sl 非空，则按照以下步骤寻找并分配座位号：
    • 初始化：设置 diff 为第一个已分配座位号与 0 的差值（即 self.sl[0] - 0），idx 为 0（表示当前考虑的座位号）。
    • 遍历座位对：利用 pairwise(self.sl) 迭代器遍历 self.sl 中的相邻座位对 (x, y)。对于每对座位，计算它们之间距离的一半（取整），即 (y - x) // 2。
      • 若此距离的一半大于 diff，则更新 diff 和 idx 分别为此距离的一半和 x + (y - x) // 2（即新座位的分配位置）。
    • 考虑最后一个座位：计算最后一个座位号 n - 1 与 self.sl 中最后一个已分配座位号之间的差值。
      • 若此差值大于 diff，则更新 diff 和 idx 分别为此差值和 n - 1（即分配最后一个座位）。
    • 添加并返回：将计算得到的座位号 idx 添加到 self.sl 中，并返回该座位号。

座位释放

• leave(self, p: int) -> None: 此方法用于释放座位号 p。
  • 它从 self.sl 中移除座位号 p。

代码实现：

from sortedcontainers import SortedList


class ExamRoom:

    def __init__(self, n: int):
        self.sl = SortedList()  # 表示已分配的座位号（有序）
        self.n = n

    def seat(self) -> int:
        # 1. 当 sl 为空时，即还没有分配座位时，分配 0 号座位
        if not self.sl:
            self.sl.add(0)
            return 0

        # 2. 当 sl 不为空时，即已经分配了若干座位（座位号有序），那么，
        # 要么分配两端的座位（0 号座位或 n - 1 号座位），
        # 要么分配两个座位号 sl[i] 和 sl[i + 1] 之间的座位：
        #   sl[i] + (sl[i + 1] - sl[i]) // 2

        # 2.1 初始分配 idx = 0 号座位，与第一个已分配座位的距离为 diff = sl[0] - 0
        # idx: 当前分配的座位号
        # diff：记录当前分配座位号与其周围（两边）已分配座位号的最大距离
        diff, idx = self.sl[0], 0

        # 2.2 分配两个座位号 sl[i] 和 sl[i + 1] 之间的座位的情况：
        #   sl[i] + (sl[i + 1] - sl[i]) // 2
        for x, y in pairwise(self.sl):
            if (y - x) // 2 > diff:
                diff = (y - x) // 2
                idx = x + (y - x) // 2

        # 2.3 分配最后一个座位号 n - 1 的情况
        if self.n - 1 - self.sl[-1] > diff:
            diff = self.n - 1 - self.sl[-1]
            idx = self.n - 1

        self.sl.add(idx)
        return idx

    def leave(self, p: int) -> None:
        self.sl.remove(p)