MockInterview:855. Exam Room

Medium

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. 1 <= N <= 10^9
2. ExamRoom.seat() and ExamRoom.leave() will be called at most 10^4 times across all test cases.
3. Calls to ExamRoom.leave(p) are guaranteed to have a student currently sitting in seat number p.

test case:

 ["ExamRoom","seat","seat","seat","seat","leave","seat"], [[10],[],[],[],[],[0],[]]

 ["ExamRoom","seat","seat","seat","seat","leave","seat"], [[10],[],[],[],[],[9],[]]

My code

class ExamRoom {
    List<Integer> arr;
    int size;
    public ExamRoom(int N) {
        arr = new LinkedList<Integer>();
        size = N;
    }
    
    public int seat() {
        int res = -1;
        if(arr.size() == 0){
            arr.add(0);
            res = 0;
        }else if(arr.size() == 1){
            int pos = arr.get(0);
            if(size - 1 - pos > pos - 0){
                arr.add(size-1);
                res = size - 1;
            }else{
                arr.add(0,0);
                res = 0;
            }
        }else{
            int pre = -1;
            int current = 0;
            int max = -1;
            int lowerPos = -1;
            int insertIndex = -1;
            while(current <= arr.size()){
                
                int minDistance = -1;
                int candidatePos = -1;
                if (pre == -1)
                {
                    int distanceRight = arr.get(current) - current;
                    minDistance = distanceRight;
                    candidatePos = 0;
                } else if (current < arr.size()) {
                    int distance = arr.get(current) - arr.get(pre);

                    int distanceLeft = distance / 2;
                    minDistance = distanceLeft;
                    candidatePos = (arr.get(current) + arr.get(pre))/2;
                } else {
                    minDistance = size - 1 - arr.get(pre);
                    candidatePos = size - 1;
                }
                
                if(minDistance > max){
                    max = minDistance;
                    lowerPos = candidatePos;
                    insertIndex = current;
                }
                
                pre = current;
                current++;
            }
            
            if(insertIndex != -1){
                arr.add(insertIndex, lowerPos);
                res = arr.get(insertIndex);
            }
            
            
                System.out.println(res);
        }
        return res;
    }
    
    public void leave(int p) {
        int left = 0;
        int right = arr.size() - 1;
        while(left <= right){
            int mid = (left+right)/2;
            if(p == arr.get(mid)){
                arr.remove(mid);
                return;
            }else if(p < arr.get(mid)){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
    }
}

Solution:
1) There are many intervals existed in the room. so define one class interval.Need to measure the min distance between the candidate and seated student(two side).There are three case. the cadidate is most left(0), mostRight(N-1), the middle of the interval. If 0 leaved, how to measure the first interval. the candidate is at mostleft, is not in the middle.so the minDistance is between candidate(0) and interval.end.
2) defined one PriorityQueue to pick up the max distance between the candidate and seated student. So we need to implement Comparable interface, and override compareTo(Object o) function. If distance is not the same, pick up the max distance, so use MaxHeap(reverse order). If the distance is the same, pick up the smaller index, so use the minHeap(normal order).
3) seat: pop the max distance interval, divide it into two parts. add two intervals.
3) leave: combine two side interval. remove two parts, add combined interval.
4) when there is no student for exam room. we need to create boundary/fake seat. which simplified the edge case.

    public class Interval implements Comparable{
        public int start;
        public int end;
        public int mid;
        public int minDistance;//if someone sit in middle, the distance between the middle and two side;
        private int N;
        public Interval(int start, int end, int N){
            this.start = start;
            this.end = end;
            this.N = N;
            if(this.start == -1){
                this.mid = 0;
                this.minDistance = this.end;
            }else if(this.end == N){
                this.mid = N - 1;
                this.minDistance = N - 1 - this.start;
            }else{
                this.mid = (end + start) / 2;
                this.minDistance = this.mid - this.start;
            }
            
            System.out.println("Created: " + this);
        }
        
        public int compareTo(Object o){
            Interval b = (Interval)o;
            if(this.minDistance != b.minDistance){
                return -(this.minDistance - b.minDistance);
            }else{
                return this.mid - b.mid;
            }
        }
        
        public String toString()
        {
            return "Start: " + this.start + " Dist: " + minDistance + " End: " + this.end + " N: " + N;
        }
    }

class ExamRoom {

    PriorityQueue<Interval> q;
    int N;
    public ExamRoom(int N) {
        q = new PriorityQueue<Interval>();
        this.N = N;
        Interval all = new Interval(-1,N,N);
        q.add(all);
    }
    
    public int seat() {
        Interval best = q.poll();
        System.out.println("Removed: " + best );
        int mid = best.mid;
        Interval interval1 = new Interval(best.start, best.mid, N);
        Interval interval2 = new Interval(best.mid, best.end, N);
        q.add(interval1);
        q.add(interval2);
        
        return mid;
    }
    
    public void leave(int p) {
        Iterator<Interval> it = q.iterator();
        Interval left = null;
        Interval right = null;
        while(it.hasNext()){
            Interval interval = it.next();
            if(interval.end == p){
                left = interval;
            }else if(interval.start == p){
                right = interval;
            }
            if(right!=null && left != null){
                Interval combine = new Interval(left.start, right.end, N);
                q.add(combine);
                break;
            }
        }
        if(right!= null && left != null){
            System.out.println("Removed: " + left + " And: " + right);
            q.remove(left);
            q.remove(right);
        }
    }
}

/**
 * Your ExamRoom object will be instantiated and called as such:
 * ExamRoom obj = new ExamRoom(N);
 * int param_1 = obj.seat();
 * obj.leave(p);
 */