855.考场就座

链接：855.考场就座
难度：Medium
标签：设计、有序集合、堆（优先队列）
简介：当学生进入考场后，他必须坐在能够使他与离他最近的人之间的距离达到最大化的座位上。如果有多个这样的座位，他会坐在编号最小的座位上。

题解 1 - python

• 编辑时间：2024-12-23
• 执行用时：96ms
• 内存消耗：21.22MB
• 编程语言：python
• 解法介绍：有序数组遍历

from sortedcontainers import SortedList
class ExamRoom:
    def getd(self, start: int, end: int) -> int:
        if end - start - 1 == 0: return 0
        if end == self.n: return self.n - start - 1
        if start == -1: return end
        mid = (end - start + 1) // 2 + start
        return min(end - mid, mid - start)
    def __init__(self, n: int):
        self.n = n
        self.arr = SortedList()
        self.arr.add((self.getd(-1, n), -1, n))
    def seat(self) -> int:
        data = self.arr.pop(0)
        start = data[1]
        end = data[2]
        if start == -1:
            self.arr.add((0, -1, 0))
            self.arr.add((-self.getd(start + 1, end), 0, end))
            return 0
        if end == self.n:
            self.arr.add((-self.getd(start, self.n - 1), start, self.n - 1))
            self.arr.add((0, self.n - 1, self.n))
            return self.n - 1
        mid = (end - start) // 2 + start
        self.arr.add((-self.getd(start, mid), start, mid))
        self.arr.add((-self.getd(mid, end), mid, end))
        return mid
    def leave(self, p: int) -> None:
        i1 = i2 = -1
        for i in range(len(self.arr)):
            if self.arr[i][2] == p: i1 = i
            if self.arr[i][1] == p: i2 = i
        start = self.arr[i1][1]
        end = self.arr[i2][2]
        self.arr.pop(max(i1, i2))
        self.arr.pop(min(i1, i2))
        self.arr.add((-self.getd(start, end), start, end))

题解 2 - cpp

• 编辑时间：2022-12-30
• 执行用时：612ms
• 内存消耗：19.8MB
• 编程语言：cpp
• 解法介绍：遍历。

class ExamRoom {
public:
    int n;
    set<int> s;
    ExamRoom(int n): n(n) {}
    int seat() {
        if (s.size() == 0) { s.insert(0); return 0; }
        auto it = s.begin(), prev = it;
        int ans = 0, val = 0;
        if (*it != 0) {
            ans = 0;
            val = *it;
        }
        for (it++; it != s.end(); prev = it++) {
            int mid = (*it + *prev) / 2;
            if (mid - *prev > val) {
                ans = mid;
                val = mid - *prev;
            }
        }
        if (*s.rbegin() != n - 1 && n - *s.rbegin() - 1 > val) {
            ans = n - 1;
            val = n - *s.rbegin() - 1;
        }
        s.insert(ans);
        return ans;
    }
    void leave(int p) {
        s.erase(p);
    }
};