C++ O(log N) for each operation, using BST(std::set) and hash table
After inserted some students, the seats would be divided into many intervals.\nWe can sort these intervals, using a complex compare function.\nTo keep the sorte
After inserted some students, the seats would be divided into many intervals.\nWe can sort these intervals, using a complex compare function.\nTo keep the sorted order after "insert" and "remove" operations, I use a BST to store these intervals.\n\nInsert operation:\n1. find the best interval (O(log n))\n2. get the middle point of the interval, split it into two intervals and insert them to the BST, remove old interval (O(log n))\n\nRemove operation (given a seat p):\n1. find the two intervals which are connected with p (O(1))\n2. delete the two intervals in the BST, and modify them in the hash table.(O(log n))\n\nTo find which interval to remove, I use a hash table, unordered_map<int, pair<set<Int, IntCmp>::iterator, set<Int, IntCmp>::iterator>>.\n\n```\nclass Int { // interval\npublic:\n    Int(int a, int b, int n) {\n        set(a, b, n);\n    }\n    void set(int a, int b, int n) {\n        st = a;\n        ed = b;\n        if (a == INT_MIN) {\n            mid = 0;\n            if (b == INT_MAX) {\n                dis = 0;\n                return;\n            }\n            dis = b;\n            return;\n        }\n        if (b == INT_MAX) {\n            mid = n - 1;\n            dis = mid - a;\n            return;\n        }\n\n        mid = (a + b) >> 1;\n        dis = min(mid - st, ed - mid);\n    }\n    int st;\n    int ed;\n    int mid;\n    int dis;\n};\n\nstruct IntCmp {\n    bool operator()(const Int& a, const Int& b) const { \n        if (a.dis != b.dis) {\n            return a.dis > b.dis;\n        }\n        if (a.mid != b.mid) {\n            return a.mid < b.mid;        \n        }\n        return (a.st == b.st) ? (a.ed < b.ed) : (a.st < b.st);\n    }\n};\n\nclass ExamRoom {\npublic:\n    int n;\n    unordered_map<int, pair<set<Int, IntCmp>::iterator, set<Int, IntCmp>::iterator>> m;\n    set<Int, IntCmp> s;\n    \n    ExamRoom(int N) {\n        n = N;\n        s.insert(Int(INT_MIN, INT_MAX, n));\n    }\n    \n    int seat() {\n        auto it = s.begin();\n        auto it1 = s.insert(Int(it->st, it->mid, n));\n        auto it2 = s.insert(Int(it->mid, it->ed, n));\n        int pos = it->mid;\n        m[pos] = make_pair(it1.first, it2.first);\n        m[it->st].second = s.find(Int(it->st, it->mid, n));\n        m[it->ed].first = s.find(Int(it->mid, it->ed, n));\n        s.erase(it);\n        return pos;\n    }\n    \n    void leave(int p) {\n        int st = m[p].first->st;\n        int ed = m[p].second->ed;\n        s.erase(m[p].first);\n        s.erase(m[p].second);\n        auto it = s.insert(Int(st, ed, n));\n        m.erase(p);\n        m[st].second = it.first;\n        m[ed].first = it.first;\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```
[]