[C++] (log n) for both operations. Using two std::sets
The basic idea is we keep current people seating in set "cur" and candidates for seating next in set "cand".\nlet\'s talk a little bit about candidate set, it i
The basic idea is we keep current people seating in set "cur" and candidates for seating next in set "cand".\nlet\'s talk a little bit about candidate set, it is a set of pair<int, int> and the first element is distance from the next person and the second element is the index. We sort this set using greater<pair<int,int>> so the cand.begin() will point out to the candidate with the greatest distance from the next person. We also use the trick of adding indexes in negative format, so they will be sorted from the left.\n```\nclass ExamRoom {\npublic:\n    int n;\n    set<int> cur;\n    set<pair<int, int>, greater<pair<int, int>>> cand;\n    ExamRoom(int N) {\n        n = N;\n    }\n    \n    void add_candidate(int a, int b) {\n        int next_idx = (a + b) / 2;\n        if (next_idx != a) {\n            cand.emplace(min(abs(b - next_idx), abs(a - next_idx)), -next_idx);\n        }\n    }\n    \n    void delete_candidate(int a, int b) {\n        int next_idx = (a + b) / 2;\n        if (next_idx != a) {\n            auto p = make_pair(min(abs(b - next_idx), abs(a - next_idx)), -next_idx);\n            cand.erase(p);\n        }\n    }\n    \n    int seat() {\n        if (cur.empty()) {\n            cur.insert(0);\n            cand.emplace(n - 1, -(n - 1));\n            return 0;\n        }\n        auto [len, idx] = *cand.begin();\n        idx = -idx;\n        cand.erase(cand.begin());\n        auto next = cur.upper_bound(idx);\n        if (next != cur.end()) {\n            add_candidate(idx, *next);\n        }\n        auto prev = cur.upper_bound(idx);\n        if (prev != cur.begin()) {\n            prev--;\n            add_candidate(*prev, idx);\n        }\n        cur.insert(idx);\n        return idx;\n        \n    }\n    \n    void leave(int p) {\n        cur.erase(p);\n        if (cur.empty()) {\n            cand.clear();\n            return;\n        }\n        int next_idx = -1, prev_idx = -1;\n        auto next = cur.upper_bound(p);\n        if (next != cur.end()) {\n            next_idx = *next;\n            delete_candidate(p, *next);\n        }\n        auto prev = cur.upper_bound(p);\n        if (prev != cur.begin()) {\n            prev--;\n            prev_idx = *prev;\n            delete_candidate(*prev, p);\n        }\n        if (cur.size() == 1) {\n            cand.clear();\n            int idx = *cur.begin();\n            if (idx != 0)\n                cand.emplace(idx, 0);\n            if (idx != n - 1)\n                cand.emplace(n - 1 - idx, -(n - 1));\n            return;\n        }\n        if (p == 0) {\n            cand.emplace(*cur.begin(), 0);\n        } else if (p == n - 1) {\n            cand.emplace(n - 1 - *cur.rbegin(), -(n - 1));\n        } else {\n            if (next_idx >= 0 && prev_idx >= 0) {\n                add_candidate(prev_idx, next_idx);\n            }\n        }\n    }\n};\n```
[]