静态网站建设的流程,申请个人网站域名,杭州比较好的互联网公司,在线代理ip题目
考场就座
在考场里#xff0c;一排有 N 个座位#xff0c;分别编号为 0, 1, 2, …, N-1 。
当学生进入考场后#xff0c;他必须坐在能够使他与离他最近的人之间的距离达到最大化的座位上。如果有多个这样的座位#xff0c;他会坐在编号最小的座位上。(另外#xf…题目
考场就座
在考场里一排有 N 个座位分别编号为 0, 1, 2, …, N-1 。
当学生进入考场后他必须坐在能够使他与离他最近的人之间的距离达到最大化的座位上。如果有多个这样的座位他会坐在编号最小的座位上。(另外如果考场里没有人那么学生就坐在 0 号座位上。)
返回 ExamRoom(int N) 类它有两个公开的函数其中函数 ExamRoom.seat() 会返回一个 int 整型数据代表学生坐的位置函数 ExamRoom.leave(int p) 代表坐在座位 p 上的学生现在离开了考场。每次调用 ExamRoom.leave§ 时都保证有学生坐在座位 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 上。
分析
寻找座位
要实时找到使间距最大化的位置可以维护一个区间的有序集合。只要能找到最大的区间就能够确定目标座位。 可以用左端点和右端点 [left, right] 表示一个区间如果一个学生坐在区间的中间那么他与两个端点的间距为 (right - left) / 2。根据题意间距相等时优先选择序号小的座位则排序区间的比较规则是
若两个区间的间距不等选择间距较大的区间
否则选择序号较小的区间可以将区间放到一个大顶堆中这样就可以在 O(1) 时间复杂度下找到满足条件的最大区间 m。当一个学生坐下时需要将 m 从大顶堆移除并根据学生坐下的位置将新产生的区间放入到大顶堆中。假设区间为 m [a, b]那么学生应该坐到 c (ab) / 2则新产生的区间为[a,c] 和 [c, b]。
离开座位
至此只分析了没有学生会离开座位的情况。如果一个学生离开了座位那么由他坐下而产生的新区间都将失效此外还需要将因为学生离开而产生的新区间放入到大顶堆中。
我们可以延迟删除大顶堆中失效的区间。
为了确定大顶堆中的区间是否失效可以设置一个有序集合 set 表示当前有学生的座位号。验证一个区间 [a, b] 有效的条件为
能从 set 里面找到 a 和 b即两个端点都有学生a 和 b 之间没有其它值即没有学生坐在这个区间里。
其它
上述分析不包含边界条件。首先想到通过在位置 -1 和位置 n 放置哨兵避免特殊情况的判断。但题目要求第一个位置为 0 号座位所以这种方法行不通。
可以单独计算学生坐在边沿的情况
如果当前没有学生就座直接选择 0 号座位如果边沿座位比某区间中央的座位更佳则选择边沿座位。
代码
struct interval {int left, right;
};struct CompByLen {bool operator()(const interval a, const interval b) const {int da a.right - a.left, db b.right - b.left;return da / 2 db / 2 || da / 2 db / 2 a.left b.left;}
};class ExamRoom {
public:ExamRoom(int n) : n_(n) {}int seat() {if (seat_taken_.empty()) {seat_taken_.insert(0);return 0;}int llen *seat_taken_.begin(), rlen n_ - 1 - *seat_taken_.rbegin();while (seat_taken_.size() 2) {auto p interval_by_len_.top();if (!isValidInterval(p)) {interval_by_len_.pop();continue;}int len p.right - p.left;if (len / 2 llen || len / 2 rlen) {// Seat on the side is better.break;}interval_by_len_.pop();int pos p.left len / 2;interval_by_len_.push({p.left, pos});interval_by_len_.push({pos, p.right});seat_taken_.insert(pos);return pos;}if (llen rlen) {interval_by_len_.push({0, *seat_taken_.begin()});seat_taken_.insert(0);return 0;} else {interval_by_len_.push({*seat_taken_.rbegin(), n_ - 1});seat_taken_.insert(n_ - 1);return n_ - 1;}}void leave(int p) {auto it seat_taken_.find(p);if (it ! seat_taken_.begin() it ! prev(seat_taken_.end())) {interval_by_len_.push({*prev(it), *next(it)});}seat_taken_.erase(it);}private:int n_;setint seat_taken_;priority_queueinterval, vectorinterval, CompByLen interval_by_len_;bool isValidInterval(interval p) {// Have students both sides no student in the middle.return seat_taken_.count(p.left) 0 seat_taken_.count(p.right) 0 *next(seat_taken_.find(p.left)) p.right;}
};
