Java TreeSet Solution: Both seat() and leave() in O(log(N)), Beating the Leetcode Solution
My idea is to maintain an ordered treeset of intervals rather than students. \nEach seat() will poll the first interval. \n\n\nclass Pair{\n\tInteger start;\n\t
My idea is to maintain an ordered treeset of intervals rather than students. \nEach seat() will poll the first interval. \n\n```\nclass Pair{\n\tInteger start;\n\tInteger end;\n\tint N;\n \n\tpublic int seat() {\n\t\tif (start == null) return 0;\n\t\tif (end == null) return N-1;\n\t\treturn (start + end) / 2;\n\t}\n\tpublic int size() {\n\t\tif (start == null && end == null) return N  ;\n\t\tif (start == null ) {\n\t\t\treturn end;\n\t\t}\n\t\tif (end == null) {\n\t\t\treturn N - 1 - start;\n\t\t}\n\t\tint mid = (start + end)/2;\n\t\treturn mid - start;\t\t\n\t} \n\t\n\tpublic Pair(int N, Integer start, Integer end) {\n\t\tthis.N = N;\n\t\tthis.start = start;\n\t\tthis.end   = end;\n\t}\n\t\n\tpublic List<Pair> split(){\n\t\tList<Pair> list = new ArrayList<>();\n\t\tif (start == null) {\n\t\t\tlist.add( new Pair(N, 0, end) );\n\t\t\treturn list;\n\t\t}\n\t\t\n\t\tif (end == null) {\n\t\t\tlist.add( new Pair (N, start,  N-1));\n\t\t\treturn list;\n\t\t}\n\t\t\n\t\t\n\t\tint mid = (start + end)/2;\n\t\tPair a = new Pair(N, start, mid);\n\t\tPair b = new Pair(N, mid, end);\n\t\t\n\t\tlist.add(a) ;\n\t\tlist.add(b) ;\n\t\treturn list;\n\t}\n}\n\nclass MyCom implements Comparator<Pair>{\n\tpublic int compare(Pair a, Pair b) {\n\t\tif (a.size()!= b.size()) {\n\t\t\treturn  - a.size() + b.size();\n\t\t}\n\t\tif (a.start == null || b.start == null) {\n\t\t\tif (a.start == null && b.start == null) {\n\t\t\t\treturn 0;\n\t\t\t}\n\t\t\tif (a.start == null) {\n\t\t\t\treturn - 1;\n\t\t\t}\n\t\t\tif (b.start == null) {\n\t\t\t\treturn 1;\n\t\t\t}\n\t\t\treturn 0;\n\t\t}\n\t\treturn a.start - b.start;\n\t}\n}\n\n\nclass ExamRoom {\n\tTreeSet<Pair> tree = new TreeSet<>(new MyCom());\n\tHashMap<Integer , Pair> startMap = new HashMap<>();\n\tHashMap<Integer , Pair> endMap = new HashMap<>();\n\tint N ; \n    public ExamRoom(int N) {\n        this.N = N;\n        Pair  p = new Pair(N, null, null);\n        tree.add(p);\n        startMap.put(null, p);\n        endMap.put(null, p);        \n    }\n    \n    public int seat() {\n        Pair pair = tree.pollFirst();\n        int ans = pair.seat();\n        startMap.remove(pair.start);\n        endMap.remove(pair.end);\n        for (Pair p: pair.split()) {\n        \ttree.add(p);\n        \tstartMap.put(p.start, p);\n        \tendMap.put(p.end, p);        \t\n        }\n        return ans;\n    }\n    \n    public void leave(int p) {\n    \tif (p == 0) {\n    \t\tPair a = startMap.get(0);\n    \t\tstartMap.remove(0);\n    \t\tendMap.remove(a.end);\n    \t\ttree.remove(a);\n    \t\t\n    \t\tPair c = new Pair(N, null, a.end);\n    \t\tstartMap.put(c.start, c);\n    \t\tendMap.put(c.end, c);\n    \t\ttree.add(c);\n    \t\treturn;\n    \t}\n    \t\n    \tif (p == N-1) {\n    \t\tPair a = endMap.get(N-1);\n    \t\tendMap.remove(N-1);\n    \t\tstartMap.remove(a.start);\n    \t\ttree.remove(a);\n    \t\t\n    \t\tPair c = new Pair(N, a.start, null);\n    \t\tstartMap.put(c.start, c);\n    \t\tendMap.put(c.end, c);\n    \t\ttree.add(c);\n    \t\treturn;\n    \t}\n    \t  \t\n    \t\n    \t\n        Pair b = startMap.get(p);\n        Pair a = endMap.get(p);\n        startMap.remove(p);\n        endMap.remove(p);\n       \n        if (a!=null) {\n        \tendMap.remove(a.end);\n            startMap.remove(a.start);\n        }\n        if (b!=null) {\n        \tstartMap.remove(b.start);\n            endMap.remove(b.end);\n        }\n        \n        tree.remove(a);\n        tree.remove(b);\n        \n        Pair c = new Pair(N, a.start, b.end);\n        startMap.put(c.start, c);\n        endMap.put(c.end, c);\n        tree.add(c);\n    } \n}\n```
['Tree', 'Java']