Java TreeMap solution, O(logn) for each operation
The major idea is to store intervals into the TreeMap, every time when we add a seat, we get the longest interval and put a seat in the middle, then break the i
The major idea is to store intervals into the TreeMap, every time when we add a seat, we get the longest interval and put a seat in the middle, then break the interval into two parts. Notice that for intervals with odd length, we simply trim it into even length using len -= len & 1.\n```\nclass ExamRoom {\n\n    TreeMap<Integer, TreeSet<Integer>> map = new TreeMap<>();\n    TreeSet<Integer> set = new TreeSet<>();\n    int N;\n    \n    public ExamRoom(int N) {\n        this.N = N;\n    }\n    \n    public int seat() {\n        int res = 0;\n        if (set.size() == 0) {\n            res = 0;\n        } else {\n            int first = set.first(), last = set.last();\n            Integer max = map.isEmpty() ? null : map.lastKey();\n            if (max == null || first >= max / 2 || N - 1 - last > max / 2) {\n                if (first >= N - 1 - last) {\n                    addInterval(0, first);\n                    res = 0;\n                } else {\n                    addInterval(last, N - 1 - last);\n                    res = N - 1;\n                }\n            } else {\n                TreeSet<Integer> temp = map.get(max);\n                int index = temp.first();\n                int next = set.higher(index);\n                int mid = (next + index) / 2;\n                removeInterval(index, max);\n                addInterval(index, mid - index);\n                addInterval(mid, next - mid);\n                res = mid;\n            }\n        }\n        set.add(res);\n        return res;\n    }\n\t\t\n    public void leave(int p) {\n        Integer pre = set.lower(p);\n        Integer next = set.higher(p);\n        set.remove(p);\n        if (next != null) {\n            removeInterval(p, next - p);\n        }\n        if (pre != null) {\n            removeInterval(pre, p - pre);\n            if (next != null) {\n                addInterval(pre, next - pre);\n            }\n        }\n    }\n\t\t\n    private void addInterval(int index, int len) {\n        len -= len & 1;  // trim to even number\n        map.putIfAbsent(len, new TreeSet<>());\n        map.get(len).add(index);\n    }\n    \n    private void removeInterval(int index, int len) {\n        len -= len & 1;\n        Set<Integer> temp = map.get(len);\n        if (temp == null) {\n            return;\n        }\n        temp.remove(index);\n        if (temp.size() == 0) {\n            map.remove(len);\n        }\n    }\n}\n```
[]