题目描述

在考场里，一排有 N 个座位，分别编号为 0, 1, 2, ..., N-1。

当学生进入考场后，他必须坐在能够使他与离他最近的人之间的距离达到最大化的座位上。如果有多个这样的座位，他会坐在编号最小的座位上。(另外，如果考场里没有人，那么学生就坐在 0 号座位上。)

返回 ExamRoom(int N) 类，它有两个公开的函数：其中，函数 ExamRoom.seat() 会返回一个 int（整型数据），代表学生坐的位置；函数 ExamRoom.leave(int p) 代表坐在座位 p 上的学生现在离开了考场。请确保每次调用 ExamRoom.leave(p) 时都有学生坐在座位 p 上。

样例

输入：["ExamRoom","seat","seat","seat","seat","leave","seat"], [[10],[],[],[],[],[4],[]]
输出：[null,0,9,4,2,null,5]
解释：
ExamRoom(10) -> null
seat() -> 0，没有人在考场里，那么学生坐在 0 号座位上。
seat() -> 9，学生最后坐在 9 号座位上。
seat() -> 4，学生最后坐在 4 号座位上。
seat() -> 2，学生最后坐在 2 号座位上。
leave(4) -> null
seat() -> 5，学生最后坐在 5 号座位上。

注意

• 1 <= N <= 10^9
• 在所有的测试样例中 ExamRoom.seat() 和 ExamRoom.leave() 最多被调用 10^4 次。
• 调用 ExamRoom.leave(p) 时需要确保当前有学生坐在座位 p 上。

算法

(暴力枚举) $O(P)$

1. 使用一个数组记录当前学生的座位号。如果数组为空，则第一个学生进入 0 号就坐。
2. 当数组非空时，需要暴力枚举整个数组来找到最大的间隔，然后插入新的位置到数组中，保持数组为升序。
3. 当有学生离开时，直接在数组里删除。

时间复杂度

• 插入和删除操作都需要遍历整个数组，故单次操作的时间复杂度为 $O(P)$，$P$ 为学生的个数。

空间复杂度

• 使用了一个额外的数组存储，故空间复杂度为 $O(P)$。

C++ 代码

class ExamRoom {
public:
    vector<int> seats;
    int n;
    ExamRoom(int N) {
        n = N;
    }

    int seat() {
        if (seats.empty()) {
            seats.push_back(0);
            return 0;
        }
        int maxDist = max(seats.front() - 0, n - 1 - seats.back());
        for (int i = 1; i < seats.size(); i++) {
            maxDist = max(maxDist, (seats[i] - seats[i - 1]) / 2);
        }
        if (maxDist == seats.front() - 0) {
            seats.insert(seats.begin(), 0);
            return 0;
        }
        for (int i = 1; i < seats.size(); i++) {
            if (maxDist == (seats[i] - seats[i - 1]) / 2) {
                seats.insert(seats.begin() + i, seats[i - 1] + maxDist);
                return seats[i];
            }
        }

        seats.push_back(n - 1);
        return n - 1;
    }

    void leave(int p) {
        for (int i = 0; i < seats.size(); i++)
            if (seats[i] == p) {
                seats.erase(seats.begin() + i);
                break;
            }
    }
};

/**
 * Your ExamRoom object will be instantiated and called as such:
 * ExamRoom obj = new ExamRoom(N);
 * int param_1 = obj.seat();
 * obj.leave(p);
 */