855. Exam Room (Medium)
https://leetcode.com/problems/exam-room/
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()
andExamRoom.leave()
will be called at most10^4
times across all test cases.- Calls to
ExamRoom.leave(p)
are guaranteed to have a student currently sitting in seat numberp
.
Solutions
class ExamRoom {
// It's not efficient to maintain the status of every seat. The better way is to keep
// all the available ranges with vacancies. For instance, N=10, execute first seat
// command, seat 0 is taken. Then available range is [1:9]; execute second seat
// command, seat 9 is taken. The available range is [1:8]; execute third seat
// command, seat 5 taken, then available ranges are [1:4] and [6,8]. For the later
// operations, just repeat above procession. Once student on seat x leaves, merge the
// two neighbor ranges. Remove the neighbor ranges and keep the newly merge bigger one.
private int N;
// use PriorityQueue to keep the maximum distance to closest person of ranges in descending order
// private Queue<Integer> sortedDist = new PriorityQueue<>((o1, o2) -> o2 - o1);
// Never use above expression, otherwise may cause overflow.
// For instance, o2 = 2147483647 and o1 = -2147483648
private Queue<Integer> sortedDist = new PriorityQueue<>(Comparator.reverseOrder());
// a bunch of ranges could have same maximum distance, so the map is 1->n, and the problem requires
// that the ranges in the front is of higher priority. so we use PriorityQueu to sort the ranges of
// same maximum distance.
private Map<Integer, PriorityQueue<Integer>> dist2RangeHeadMap = new HashMap<>();
// anchor for particular range, locating by head index
private Map<Integer, Range> head2RangeMap = new HashMap();
// anchor for particular range, locating by tail index
private Map<Integer, Range> tail2RangeMap = new HashMap();
public ExamRoom(int N) {
this.N = N;
}
public int seat() {
if (dist2RangeHeadMap.size() == 0) {
Range range = new Range(1, N - 1);
addRange(range);
return 0;
}
int maxRange = sortedDist.peek();
int rangeHead = dist2RangeHeadMap.get(maxRange).peek();
Range range = head2RangeMap.get(rangeHead);
int seat = range.seat;
// remove range at first
removeRange(range);
// split current range into two sub range
// left neighbor range
Range range1 = new Range(rangeHead, seat - 1);
if (range1.maxDist >= 1) {
addRange(range1);
}
// right neighbor range
Range range2 = new Range(seat + 1, range.tail);
if (range2.tail < N && range2.maxDist >= 1) {
addRange(range2);
}
return seat;
}
public void leave(int p) {
int leftRangeTail = p - 1;
int rightRangeHead = p + 1;
Range leftRange = null;
Range rightRange = null;
// combine neighbor ranges
if (tail2RangeMap.containsKey(leftRangeTail)) {
leftRange = tail2RangeMap.get(leftRangeTail);
}
if (head2RangeMap.containsKey(rightRangeHead)) {
rightRange = head2RangeMap.get(rightRangeHead);
}
if (leftRange == null && rightRange == null) {
Range range = new Range(p, p);
addRange(range);
}
// delete neighbor ranges
if (leftRange != null) {
removeRange(leftRange);
}
if (rightRange != null) {
removeRange(rightRange);
}
if (leftRange != null && rightRange == null) {
Range range = new Range(leftRange.head, p);
addRange(range);
}
if (leftRange == null && rightRange != null) {
Range range = new Range(p, rightRange.tail);
addRange(range);
}
if (leftRange != null && rightRange != null) {
Range range = new Range(leftRange.head, rightRange.tail);
addRange(range);
}
}
private void removeRange(Range range) {
// remove this range
dist2RangeHeadMap.get(range.maxDist).remove(range.head);
// remove the head of this range
head2RangeMap.remove(range.head);
// remove the tail of this range
tail2RangeMap.remove(range.tail);
// the max range is unique
if (dist2RangeHeadMap.get(range.maxDist).size() == 0) {
sortedDist.remove(range.maxDist);
}
}
private void addRange(Range range) {
if (!sortedDist.contains(range.maxDist)) {
sortedDist.offer(range.maxDist);
}
if (!dist2RangeHeadMap.containsKey(range.maxDist)) {
dist2RangeHeadMap.put(range.maxDist, new PriorityQueue<>());
}
dist2RangeHeadMap.get(range.maxDist).offer(range.head);
head2RangeMap.put(range.head, range);
tail2RangeMap.put(range.tail, range);
}
class Range {
// the start position of the range
public int head;
// the end position of the range
public int tail;
// the size of the range
public int size;
// the best seat of the range, could be the middle or head or tail
public int seat;
// from head to seat, or seat to tail, the max distance it can be
// to closest people. think seriously about both odd or even size
// of range.
public int maxDist;
public Range(int head, int tail) {
this.head = head;
this.tail = tail;
this.size = tail - head + 1;
// the range starts from 0
if (head == 0) {
seat = 0;
maxDist = tail - seat + 1;
} else if (tail == N - 1) { // range ends at N-1
seat = N - 1;
maxDist = seat - head + 1;
} else { // above two are special cases, this is ordinary one which chooses the middle
seat = (int)((tail * 1l + head * 1l) / 2);
maxDist = Math.min(seat - head + 1, tail - seat + 1);
}
}
// rewrite following two functions
@Override
public boolean equals(Object o) {
if (!(o instanceof Range)) {
return false;
}
Range r = (Range) o;
return r.head == head && r.tail == tail;
}
@Override
public int hashCode() {
return (head + "#" + tail).hashCode();
}
}
}