[Java/C++] Short TreeSet PriorityQueue Lambda O(logn) solution with explanation
define a triplet(dist, pre, suc) as a gap. dist = (suc - pre) / 2\n- only put gap with dist >= 1 to the pq. dist == 0 means there is no gap\n- when poll from pq
- define a triplet(dist, pre, suc) as a gap. dist = (suc - pre) / 2\n- only put gap with dist >= 1 to the pq. dist == 0 means there is no gap\n- when poll from pq, check the pre and suc of this gap exist and next to each other in the TreeSet or not. If not, discard this gap.\n```java\nclass ExamRoom {\n\n    int N;\n    TreeSet<Integer> set = new TreeSet<>();\n    PriorityQueue<int[]> pq;\n    \n    public ExamRoom(int N) {\n        this.N = N;\n        pq = new PriorityQueue<int[]>(Comparator.comparing((int[] v) -> -v[0]).thenComparing((int[] v) -> v[1]));\n    }\n    \n    public int seat() {\n        if (set.size() == 0){\n            set.add(0);\n            return 0;\n        } \n        int first = set.first();\n        int len = first - 0;\n        int can = 0;\n        int last = set.last();\n        if (N - 1 - last > len){\n            len = N - 1 - last;\n            can = N - 1;\n        }\n        boolean found = false;\n        while (!found && pq.size() > 0){\n            int[] arr = pq.poll();\n            if (set.contains(arr[1])){\n                Integer higher = set.higher(arr[1]);\n                if (higher != null && higher.equals(arr[2])){\n                    found = true;\n                    if (arr[0] > len || (arr[0] == len && arr[0] + arr[1] < can)){\n                        can = arr[0] + arr[1];\n                        set.add(can);\n                        if (arr[2] - can > 1){\n                            pq.offer(new int[]{(arr[2] - can) / 2, can, arr[2]});\n                        }\n                        if (can - arr[1] > 1){\n                            pq.offer(new int[]{(can - arr[1]) / 2, arr[1], can});\n                        }\n                        return can;\n                    } else {\n                        pq.offer(arr);\n                    }\n                }\n            }\n        }\n        set.add(can);\n        if (first - can > 1){\n            pq.offer(new int[]{(first - can) / 2, can, first});\n        } \n        if (can - last > 1){\n            pq.offer(new int[]{(can - last) / 2, last, can});\n        }\n        return can;\n    }\n    \n    public void leave(int p) {\n        Integer lower = set.lower(p);\n        Integer higher = set.higher(p);\n        if (lower != null && higher != null){\n            pq.offer(new int[]{(higher - lower) / 2, lower, higher});\n        }\n        set.remove(p);\n    }\n}\n```\n\n```c++\nclass mycompare{\npublic:\n    bool operator() (const vector<int> & lhs, const vector<int> & rhs){\n        if (lhs[0] != rhs[0]){\n            return lhs[0] < rhs[0];\n        } else {\n            return lhs[1] > rhs[1];\n        }\n    }\n};\n\nclass ExamRoom {\nprivate:\n    set<int> st;\n    priority_queue<vector<int>, vector<vector<int>>, mycompare> pq;\n    int N;\npublic:\n    ExamRoom(int N) {\n        this->N = N;\n    }\n    \n    int seat() {\n        if (st.size() == 0){\n            st.insert(0);\n            return 0;\n        }\n        int first = *st.begin();\n        int last = *st.rbegin();\n        int can = 0;\n        int len = first - 0;\n        if (N - 1 - last > len){\n            len = N - 1 - last;\n            can = N - 1;\n        }\n        bool found = false;\n        while (!found && pq.size() > 0){\n            auto cur = pq.top();\n            // check valid\n            auto it = st.find(cur[1]);\n            if (it != st.end() && ++it != st.end() && *it == cur[2]){\n                // check if it\'s a candidate\n                found = true;\n                if (cur[0] > len || (cur[0] == len && cur[0] + cur[1] < can)){\n                    can = cur[0] + cur[1];\n                    len = cur[0];\n                    \n                    if (cur[2] - can > 1){\n                        pq.push({(cur[2] - can) / 2, can, cur[2]});\n                    }\n                    if (can - cur[1] > 1){\n                        pq.push({(can - cur[1]) / 2, cur[1], can});\n                    }\n                    st.insert(can);\n                    pq.pop();\n                    return can;\n                }\n            } else {\n                pq.pop();\n            }\n        }\n        st.insert(can);\n        if (first - can > 1){\n            pq.push({(first - can) / 2, can, first});\n        } \n        if (can - last > 1){\n            pq.push({(can - last) / 2, last, can});\n        }\n        return can;\n    }\n    \n    void leave(int p) {\n        auto cur = st.find(p);\n        if (--cur != st.end()){\n            int pre = *cur;\n            auto suc = st.upper_bound(p);\n            if (suc != st.end() && *suc - pre > 1){\n                pq.push({(*suc - pre) / 2, pre, *suc});\n            }\n        }\n        st.erase(st.find(p));\n    }\n};\n```
[]