Exam Room

Problem

Exam Room

Approach

This approach is to record all the chose seat numbers, which are very useful to decide the next available number. More specifically, we just need to go through these numbers and every time choose two consecutive ones to calculate the distance between them. After one iteration, we can get the best choice required by the problem.

More importantly, we have to deal with the two numbers in different ways, 0 and N - 1. Because if they aren’t chosen, they won’t be taken into consideration.

Code

class ExamRoom {
    
    int n;
    TreeSet<Integer> nums;

    public ExamRoom(int N) {
        n = N - 1;
        nums = new TreeSet<>();
    }
    
    public int seat() {
        if(nums.isEmpty()){
            nums.add(0);
            return 0;
        }
        Iterator<Integer> it = nums.iterator();
        int pre = it.next(), maxGap = 0, target = 0;
        while(it.hasNext()){
            int cur = it.next();
            int mid = (int)((cur + pre)/2);
            if(Math.min(mid - pre, cur - mid) > maxGap){
                maxGap = Math.min(mid - pre, cur - mid);
                target = mid;
            }
            pre = cur;
        }
        // check if 0th and nth element exist in the array
        if(!nums.contains(0)){
            int gap = nums.first();
            if(gap >= maxGap){
                maxGap = gap;
                target = 0;
            }
        }
        if(!nums.contains(n)){
            int gap = n - nums.last();
            if(gap > maxGap){
                maxGap = gap;
                target = n;
            }
        }
        nums.add(target);
        return target;
    }
    
    public void leave(int p) {
        nums.remove(p);
    }
}

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