/**
* In an exam room, there are N seats in a single row, numbered 0, 1, 2, ..., N-1.
*
* When a student enters the room, they must sit in the seat that maximizes the
* distance to the closest person. If there are multiple such seats, they sit
* in the seat with the lowest number. (Also, if no one is in the room, then
* the student sits at seat number 0.)
*
* Return a class ExamRoom(int N) that exposes two functions: ExamRoom.seat()
* returning an int representing what seat the student sat in, and
* ExamRoom.leave(int p) representing that the student in seat number p now
* leaves the room. It is guaranteed that any calls to ExamRoom.leave(p) have
* a student sitting in seat p.
*
* Example 1:
* Input: ["ExamRoom","seat","seat","seat","seat","leave","seat"], [[10],[],[],[],[],[4],[]]
* Output: [null,0,9,4,2,null,5]
*
* Explanation:
* ExamRoom(10) -> null
* seat() -> 0, no one is in the room, then the student sits at seat number 0.
* seat() -> 9, the student sits at the last seat number 9.
* seat() -> 4, the student sits at the last seat number 4.
* seat() -> 2, the student sits at the last seat number 2.
* leave(4) -> null
* seat() -> 5, the student​​​​​​​ sits at the last seat number 5.
​​​​​​​ *
* Note:
* 1 <= N <= 10^9
* ExamRoom.seat() and ExamRoom.leave() will be called at most 10^4 times across all test cases.
* Calls to ExamRoom.leave(p) are guaranteed to have a student currently sitting in seat number p.
*/
public class ExamRoom855 {
class ExamRoom {
private PriorityQueue pq;
private Map lefts;
private Map rights;
private int N;
public ExamRoom(int N) {
this.pq = new PriorityQueue(1, new Comparator() {
@Override
public int compare(Range r1, Range r2) {
int rangeDiff = Integer.compare(dis(r2), dis(r1));
if (rangeDiff != 0) return rangeDiff;
return Integer.compare(r1.left, r2.left);
}
});
this.lefts = new HashMap<>();
this.rights = new HashMap<>();
this.N = N;
Range first = new Range(-1, N);
this.pq.add(first);
this.lefts.put(first.left, first);
this.rights.put(first.right, first);
}
public int seat() {
if (this.pq.isEmpty()) return -1;
Range curr = this.pq.poll();
this.lefts.remove(curr.left);
this.rights.remove(curr.right);
int pos = sitPos(curr);
Range l = new Range(curr.left, pos);
this.lefts.put(l.left, l);
this.rights.put(l.right, l);
if (curr.left + 1 < pos) {
this.pq.add(l);
}
Range r = new Range(pos, curr.right);
this.lefts.put(r.left, r);
this.rights.put(r.right, r);
if (pos + 1 < curr.right) {
this.pq.add(r);
}
return pos;
}
public void leave(int p) {
Range r = this.lefts.get(p);
Range l = this.rights.get(p);
this.pq.remove(r);
this.pq.remove(l);
Range merged = new Range(l.left, r.right);
this.pq.add(merged);
this.lefts.put(merged.left, merged);
this.rights.put(merged.right, merged);
}
private int sitPos(Range r) {
return sitPos(r.left, r.right);
}
private int sitPos(int left, int right) {
if (left + 1 >= right) return -1;
if (left < 0) return 0;
if (right >= this.N) return this.N - 1;
return (right - left) / 2 + left;
}
private int dis(Range r) {
return dis(r.left, r.right);
}
private int dis(int left, int right) {
if (left < 0) return right;
if (right >= this.N) return this.N - 1 - left;
return (right - left) / 2;
}
}
class Range {
int left;
int right;
Range (int l, int r) {
this.left = l;
this.right = r;
}
}
/**
* Your ExamRoom object will be instantiated and called as such:
* ExamRoom obj = new ExamRoom(N);
* int param_1 = obj.seat();
* obj.leave(p);
*/
}