跳到主要内容

855.考场就座

· 阅读需 4 分钟

1、题干​

在考场里，一排有 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. 1 <= N <= 10^9
  2. 在所有的测试样例中 ExamRoom.seat() 和 ExamRoom.leave() 最多被调用 10^4 次。
  3. 保证在调用 ExamRoom.leave(p) 时有学生正坐在座位 p 上。

2、代码​

class ExamRoom {
    n = -1;
    min = Infinity;
    max = -Infinity;
    set = new Set<number>();
    pq = new PriorityQueue({
        compare: (a: [number, number], b: [number, number]): number => {
            const da = (a[1] - a[0]) / 2 >> 0, db = (b[1] - b[0]) / 2 >> 0;
            return da !== db ? db - da : a[0] - b[0];
        }
    });

    constructor(n: number) {
        this.n = n;
    }

    seat(): number {
        let i = 0;
        if (this.set.size) {
            let found = false;
            while (!found && this.pq.size()) {
                const [n1, n2] = this.pq.dequeue();
                if (n2 - n1 < 1 || !this.set.has(n1) || !this.set.has(n2)) continue;

                const [m1, m2] = this.pq.front() || [];
                if (n1 === m1 && n2 === m2) continue;

                i = (n1 + n2) / 2 >> 0;
                if (this.set.has(i) && this.set.has(i + 1)) continue;

                if ((n2 - n1) / 2 >> 0 <= this.min || (n2 - n1) / 2 >> 0 < this.n - 1 - this.max) {
                    this.pq.enqueue([n1, n2]);
                    break;
                }

                found = true;
                if (this.set.has(i)) i = i + 1;

                this.pq.enqueue([n1, i]);
                this.pq.enqueue([i, n2]);
            }

            if (!found) {
                if (this.n - 1 - this.max > this.min) {
                    i = this.n - 1;
                    this.pq.enqueue([this.max, i]);
                } else {
                    i = 0;
                    this.pq.enqueue([i, this.min]);
                }
            }
        }

        this.set.add(i);
        if (i < this.min) this.min = i;
        if (i > this.max) this.max = i;
        return i;
    }

    leave(p: number): void {
        this.set.delete(p);
        const nums = [...this.set].sort((a, b) => a - b);

        this.min = !nums.length ? Infinity : nums[0];
        this.max = !nums.length ? -Infinity : nums[nums.length - 1];

        const i = nums.findIndex(n => n > p);
        if (i > 0) this.pq.enqueue([nums[i - 1], nums[i]]);
    }
}

3、执行结果​

image.png