Java TreeSet
\n\n\nclass ExamRoom {\n    int n;    \n    \n    class Interval {\n        int l;\n        int r;\n        int dis;\n        boolean isStart;\n        boolean 
```\n\n\nclass ExamRoom {\n    int n;    \n    \n    class Interval {\n        int l;\n        int r;\n        int dis;\n        boolean isStart;\n        boolean isEnd;\n        \n        Interval(int l, int r) {\n            this.l = l;\n            this.r = r;\n            if(l == -1) {\n                this.dis = r;\n                isStart = true;\n            } else if(r == n) {\n                this.dis = n-1-l;\n                isEnd = true;\n            } else {\n                this.dis = (r - l)/2;\n            }\n        }\n    }\n    \n    Map<Integer, Interval> leftIntervals;\n    Map<Integer, Interval> rightIntervals;\n    TreeSet<Interval> intervals;\n    \n    public ExamRoom(int n) {\n        this.n = n;\n        leftIntervals = new HashMap();\n        rightIntervals = new HashMap();\n        intervals = new TreeSet<Interval>((a,b)->{\n            if(a.dis > b.dis) return -1;\n            if(a.dis < b.dis) return 1;\n            // if(a.dis == b.dis) {\n            //     if(a.l <= b.l) return -1;\n            // }\n            \n            return a.l - b.l;\n        });\n        \n        intervals.add(new Interval(-1, n));\n    }\n    \n    public int seat() {\n        Interval largest = intervals.first();\n        // System.out.println("largest l:" + largest.l + " r:" + largest.r + " isStart:" + largest.isStart);\n        int seat = -1;\n        if(largest.isStart) {\n            seat = 0;\n        } else if(largest.isEnd) {\n            seat = n-1;\n        } else {\n            seat = largest.l + largest.dis;\n        }\n        \n        removeInterval(largest);\n        \n        if(seat != 0) {\n            Interval newLeft = new Interval(largest.l, seat);\n            addInterval(newLeft);\n            // System.out.println("left dis:" + newLeft.dis + " l:" + newLeft.l + " r:" + newLeft.r);\n        }\n        \n        if(seat != n-1) {\n            Interval newRight = new Interval(seat, largest.r);\n            addInterval(newRight);\n            // System.out.println("right dis:" + newRight.dis + " l:" + newRight.l + " r:" + newRight.r);\n        }\n        \n        // System.out.println("intervals first:" + intervals.first().l + " seat:" + seat);\n        \n        return seat;\n    }\n    \n    public void leave(int p) {\n        Interval left = leftIntervals.get(p);\n        Interval right = rightIntervals.get(p);\n   \n        int l = -1;\n        int r = n;\n        \n        if(left != null) {\n            l = left.l;\n            removeInterval(left);\n        }\n        \n        if(right != null) {\n            r = right.r;\n            removeInterval(right);\n        }\n        \n        addInterval(new Interval(l, r));\n    }\n    \n    private void removeInterval(Interval interval) {\n        intervals.remove(interval);\n        // System.out.println("After remove intervals:" + intervals + " to remove:" + interval);\n        leftIntervals.remove(interval.r);\n        rightIntervals.remove(interval.l);\n    }\n    \n    private void addInterval(Interval interval) {\n        intervals.add(interval);\n        if(interval.r != n) leftIntervals.put(interval.r, interval);\n        if(interval.l != -1) rightIntervals.put(interval.l, interval);\n    }\n}\n\n/**\n * Your ExamRoom object will be instantiated and called as such:\n * ExamRoom obj = new ExamRoom(n);\n * int param_1 = obj.seat();\n * obj.leave(p);\n */\n```
[]