[C++] O(logn) for both leave and seat using hash map and set
First let\'s define a segment to be a tuple of {start, end} indicating that the seats between start and end (inclusive) are available. When a student is taking 
First let\'s define a segment to be a tuple of `{start, end}` indicating that the seats between `start` and `end` (inclusive) are available. When a student is taking a seat, in order to maximize the distance to the closest student, we must find the **largest** available segment.  Initially, all seats are empty, so the starting segment is simply `{0, n - 1}`.\n\nSo for `seat()`, the problem comes down to how we can efficiently compute the largest available segment, then we can easily figure out the seat index by taking the middle seat of the segment. Binary search tree is a suitable data structure here because it lets us find largest / smaller element in `O(logn)`.\n\n`leave()` is trickier, since by leaving a seat `p`, we need to merge any existing segments that are adjacent to `p`:\n\nWhen a student leaves seat `p`, we need to merge *at most* two segments that are adjacent to `p` :\n+ if there is a segment ending at `p - 1` (`first half`) and another starting at `p + 1` (`second half`), our resulting segment is the `{start of first half, end of second half}`\n+ if there is only the first half, then it is `{start of first half, p}`\n+ if there is only the second half, then it is `{p, end of second half}`\n+ if there aren\'t any adjacent segments, simply use `{p, p}`\n\nTo keep track of adjacent segments, we can use two `unordered_maps` that map from the either the start or end of a segment to its corresponding iterator in the `set`. This allows us to merge adjacent segments and update the `set` in `O(logn)` time as well.\n\n```c++\nstruct cmp {\n    \n    const int n;\n    \n    cmp(int n): n(n) {}\n    \n    int getMid(pair<int, int> p1) const {\n        if (p1.first == 0 || p1.second == n - 1) {\n            return p1.second - p1.first;\n        } else {\n            return (p1.second - p1.first) / 2;\n        }\n    }\n    \n    bool operator()(pair<int, int> p1, pair<int, int> p2) const {\n        int m1 = getMid(p1);\n        int m2 = getMid(p2);\n        \n        if (m1 == m2) {\n            return p1.first < p2.first;\n        }\n        \n        return m1 > m2;\n    }\n};\n\nclass ExamRoom {\n    \n    using iterator = set<pair<int, int>, cmp>::iterator;\n    set<pair<int, int>, cmp> s;\n    unordered_map<int, iterator> starts;\n    unordered_map<int, iterator> ends;\n    \n    const int n;\n    \n    void insert(pair<int, int> p) {\n        auto [start, end] = p;\n        auto [it, inserted] = s.insert({start, end});\n        starts[start] = it;\n        ends[end] = it;\n    }\n    \n    void erase(pair<int, int> p) {\n        auto [start, end] = p;\n        s.erase({start, end});\n        starts.erase(start);\n        ends.erase(end);\n    }\n    \npublic:\n    ExamRoom(int n): s(cmp(n)), n(n) {\n        s.insert({0, n - 1});\n    }\n    \n    int seat() {\n        auto [start, end] = *s.begin();\n        erase(*s.begin());\n        \n        int mid;\n        \n        if (start == 0) {\n            mid = 0;\n        } else if (end == n - 1) {\n            mid = n - 1;\n        } else {\n            mid = start + (end - start) / 2;\n        }\n\n        if (mid > start) {\n            insert({start, mid - 1});\n        }\n\n        if (mid < end) {\n            insert({mid + 1, end});\n        }\n        \n        return mid;\n    }\n    \n    void leave(int p) {\n        int start = p;\n        int end = p;\n\n        if (ends.count(p - 1)) {\n            auto firstHalf = ends[p - 1];\n            auto [firstHalfStart, firstHalfEnd] = *firstHalf;\n            erase(*firstHalf);\n            start = firstHalfStart;\n        }\n\n        if (starts.count(p + 1)) {\n            auto secondHalf = starts[p + 1];\n            auto [secondHalfStart, secondHalfEnd] = *secondHalf;\n            erase(*secondHalf);\n            end = secondHalfEnd;\n        }\n\n        insert({start, end});\n    }\n};\n```
[]