it's ugly but it's mine - O(log(n))
I\'m maintaing a set of pair of available seats. We also have a map of int to set>, which stores size to available ranges of that size. \n\nI specially need to 
I\'m maintaing a set of pair<int, int> of available seats. We also have a map of int to set<pair<int, int>>, which stores size to available ranges of that size. \n\nI specially need to handle the code for first and last seat, rest of it is pretty simple. We will either use the first range from largest size, or the first range from second largest size.\n\nTime complexity: O(log(n)) for each call\n# Code\n```cpp []\nstruct RangeSet {\n    int n, INF;\n    set<pair<int, int>> ranges;\n    map<int, set<pair<int, int>>> sizes;\n\n    RangeSet(int n) {\n        this->n = n;\n        INF = 1e9 + 5;\n        ranges.insert({-INF, -INF});\n        ranges.insert({INF, INF});\n        addRange(0, n - 1);\n    }\n\n    void addRange(int l, int r) {\n        int sz = r - l + 1;\n        ranges.insert({l, r});\n        sizes[sz].insert({l, r});\n    }\n\n    set<pair<int, int>>::iterator removeRange(set<pair<int, int>>::iterator& it) {\n        int l = it->first, r = it->second, sz = r - l + 1;\n        sizes[sz].erase({l, r});\n        if (sizes[sz].empty()) {\n            sizes.erase(sz);\n        }\n        return ranges.erase(it);\n    }\n\n    void insert(int x) {\n        int L = x, R = x;\n        auto it = ranges.lower_bound({L + 1, L + 1});\n        it = prev(it);\n\n        if (it->first <= L && L <= it->second + 1) {\n            L = it->first;\n            it = removeRange(it);\n        } else {\n            it = next(it);\n        }\n        if (it->first - 1 <= R && R <= it->second) {\n            R = it->second;\n            removeRange(it);\n        }\n        addRange(L, R);\n    }\n\n    void erase(int x) {\n        auto it = ranges.lower_bound({x + 1, x + 1});\n        it = prev(it);\n        if (it->first <= x && x <= it->second) {\n            if (it->first < x) {\n                addRange(it->first, x - 1);\n            }\n            if (x < it->second) {\n                addRange(x + 1, it->second);\n            }\n            removeRange(it);\n            return;\n        }\n    }\n\n    pair<int, int> findFirstCandidateRange() {\n        auto largest = prev(sizes.end());\n        return *largest->second.begin();\n    }\n\n    pair<int, int> findSecondCandidateRange() {\n        auto largest = prev(sizes.end());\n        int sz = largest->first;\n        auto it = sizes.find(sz - 1);\n        if (it == sizes.end()) {\n            return {INF, INF};\n        }\n        return *it->second.begin();\n    }\n\n    int findBestSeat() {\n        map<int, int> cand;\n        bool isFirstTaken = next(ranges.begin())->first != 0;\n        bool isLastTaken = prev(prev(ranges.end()))->second != n - 1;\n\n        if (!isFirstTaken) {\n            auto [al, ar] = *next(ranges.begin());\n            int dist = ((ar + 1 == n) ? INF : ar + 1);\n            cand[0] = dist;\n        }\n\n        if (!isLastTaken) {\n            auto [al, ar] = *prev(prev(ranges.end()));\n            int d = n - 1 - (al - 1);\n            int dist = (d == n ? INF : d);\n            cand[n - 1] = dist; \n        }\n\n        auto findDist = [](int l, int r) {\n            return r - l;\n        };\n\n        auto [l1, r1] = findFirstCandidateRange();\n        auto [l2, r2] = findSecondCandidateRange();\n        int seat1 = (l1 + r1) / 2, seat2 = (l2 + r2) / 2;\n        int dist1 = min(seat1 - l1 + 1, r1 - seat1 + 1);\n        int dist2 = seat2 != INF ? min(seat2 - l2 + 1, r2 - seat2 + 1) : -INF;\n\n        int bestSeat = -1;\n        if (!cand.count(seat1)) {\n            cand[seat1] = dist1; \n        }\n        if (seat2 != INF && !cand.count(seat2)) {\n            cand[seat2] = dist2; \n        }\n\n        int maxDist = INT_MIN;\n        for (auto& [seat, dist] : cand) {\n            if (dist > maxDist) {\n                maxDist = dist;\n                bestSeat = seat;\n            }\n        }\n        erase(bestSeat);\n        return bestSeat;\n    }\n};\n\nclass ExamRoom {\npublic:\n    RangeSet rs;\n\n    ExamRoom(int n) : rs(n) {}\n\n    int seat() {\n        return rs.findBestSeat();\n    }\n\n    void leave(int p) {\n        rs.insert(p);\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```
['C++']