题目：
在考场里，一排有 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上。
思路：
代码：
struct Comp {
bool operator()(const pair<int, int> &p1, const pair<int, int> &p2) {
int d1 = p1.second - p1.first, d2 = p2.second - p2.first;
return d1 / 2 < d2 / 2 || (d1 / 2 == d2 / 2 && p1.first > p2.first);
}
};
class ExamRoom {
private:
int n;
set<int> seats;
priority_queue<pair<int, int>, vector<pair<int, int>>, Comp> pq;
public:
ExamRoom(int n) : n(n) {
}
int seat() {
if (seats.empty()) {
seats.insert(0);
return 0;
}
int left = *seats.begin(), right = n - 1 - *seats.rbegin();
while (seats.size() >= 2) {
auto p = pq.top();
if (seats.count(p.first) > 0 && seats.count(p.second) > 0 &&
*next(seats.find(p.first)) == p.second) { // 不属于延迟删除的区间
int d = p.second - p.first;
if (d / 2 < right || d / 2 <= left) { // 最左或最右的座位更优
break;
}
pq.pop();
pq.push({p.first, p.first + d / 2});
pq.push({p.first + d / 2, p.second});
seats.insert(p.first + d / 2);
return p.first + d / 2;
}
pq.pop(); // leave 函数中延迟删除的区间在此时删除
}
if (right > left) { // 最右的位置更优
pq.push({*seats.rbegin(), n - 1});
seats.insert(n - 1);
return n - 1;
} else {
pq.push({0, *seats.begin()});
seats.insert(0);
return 0;
}
}
void leave(int p) {
if (p != *seats.begin() && p != *seats.rbegin()) {
auto it = seats.find(p);
pq.push({*prev(it), *next(it)});
}
seats.erase(p);
}
};