【Leetcode】855. 考场就座

题目

题目链接🔗
在考场里，有 $n$ 个座位排成一行，编号为 $0$ 到 $n-1$。

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

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

实现 $ExamRoom$ 类：

$ExamRoom(intn)$ 用座位的数量 n 初始化考场对象。
$intseat()$ 返回下一个学生将会入座的座位编号。
$voidleave(intp)$ 指定坐在座位 $p$ 的学生将离开教室。保证座位 $p$ 上会有一位学生。
示例 1：

输入：
[“ExamRoom”, “seat”, “seat”, “seat”, “seat”, “leave”, “seat”]
[[10], [], [], [], [], [4], []]
输出： [null, 0, 9, 4, 2, null, 5]
解释：
ExamRoom examRoom = new ExamRoom(10); examRoom.seat(); // 返回 0，房间里没有人，学生坐在 0 号座位。
examRoom.seat(); // 返回 9，学生最后坐在 9 号座位。
examRoom.seat(); // 返回 4，学生最后坐在 4 号座位。 examRoom.seat(); // 返回 2，学生最后坐在2 号座位。
examRoom.leave(4);
examRoom.seat(); // 返回 5，学生最后坐在 5 号座位。

提示：

1. $1\le n\le 10^9$
2. 保证有学生正坐在座位 $p$ 上。
3. $seat$ 和 $leave$ 最多被调用 $10^4$ 次。

思路

这个问题可以通过模拟的方式来解决。我们需要维护一个座位集合，每次调用 seat() 时，找到第一个满足条件的座位分配给学生，并在调用 leave(int p) 时，释放该座位。

代码

class ExamRoom {
public:
    set<int>st;
    int n;
    ExamRoom(int N) {
        n = N;
    }
    
    int seat() {
        if (st.empty()) {
            st.insert(0); return 0;
        }
        int pre = *st.begin(), idx = 0, mx = pre;
        for (auto u : st) {
            if ((u - pre) / 2 > mx) {
                idx = (u + pre) / 2;
                mx = (u - pre) / 2;
            }
            pre = u; 
        }
        if (n - 1 - pre > mx) {
            idx = n - 1;
        }
        st.insert(idx);
        return idx;
    }
    
    void leave(int p) {
        st.erase(p);

    }
};

复杂度分析

时间复杂度

$O(N)$，其中 $N$ 是座位集合 $st$ 的大小。

空间复杂度

$O(N)$，需要存储所有已占用的座位编号。

结果

总结

本题是一个模拟题，关键在于理解如何模拟座位的分配和释放过程。通过维护一个座位集合，我们可以有效地找到满足条件的座位，并在学生离开时释放座位。这种方法简单且高效，适用于需要管理有限资源的场景。