https://leetcode.com/problems/exam-room/
    class Interval {
        int start, end, mid,dis;
        Interval(int start, int end) {
            this.start = start;
            this.end = end;
            mid = start - (start - end) / 2;
            if (start == -1) { // special case head and tail
                dis = end;
            } else if (end == N) {
                dis = N - start - 1;
            } else {
                dis = mid - start;
            }
        }
    }

    Interval interval;
    Queue<Interval> pq;
    int N;
    // Map<Integer,Interval> startMap;
    // Map<Integer,Interval> endMap;

    public ExamRoom(int N) {
        // startMap = new HashMap<>();
        // endMap = new HashMap<>();
        interval = new Interval(-1, N);
        pq = new PriorityQueue<>((a,b)-> {
            if (b.dis == a.dis) {
                return a.mid - b.mid;
            } else {
                return b.dis - a.dis;
            }
        });
        pq.offer(interval);
        this.N = N;
    }

    public int seat() { //O(logn) 
        //if (pq.isEmpty()) return -1;
        interval = pq.poll();
        Interval i1,i2;
        if (interval.start == -1) {
            i1= new Interval(-1, 0);
            i2 = new Interval(0, interval.end);  
        } else if (interval.end == N) {
            i1 = new Interval(interval.start, N-1);
            i2 = new Interval(N-1, N);
        } else {
            i1 = new Interval(interval.start, interval.mid);
            i2 = new Interval(interval.mid, interval.end);
        }
        pq.offer(i1);
        pq.offer(i2);
        // startMap.put(i1.start, i1);
        // startMap.put(i2.start, i2);
        // endMap.put(i1.end, i1);
        // endMap.put(i2.end, i2);
        return i1.end;

    }

    public void leave(int p) { //O(n) or O(logn) with startMap
        List<Interval> list = new ArrayList<>(pq);
        Interval i1 = null,i2 = null;
        for (Interval interval: list) {
            if (interval.end == p) {
                i1 = interval;
            } else if (interval.start == p) {
                i2 = interval;
            }
        }
        // i1 = endMap.getOrDefault(p,null);
        // i2 = startMap.getOrDefault(p,null);
        // startMap.remove(i1.start);
        // startMap.remove(i2.start);
        // endMap.remove(i1.end);
        // endMap.remove(i2.end);
        pq.remove(i1);
        pq.remove(i2);
        Interval newInterval = new Interval(i1.start, i2.end);
        // startMap.put(i1.start,newInterval);
        // endMap.put(i2.end,newInterval);
        pq.offer(newInterval);

    }
}

/**
 * ExamRoom obj = new ExamRoom(N);
 * int param_1 = obj.seat();
 * obj.leave(p);
 */