log(n) for both seat and leave in c++
The basic idea is we build a tree set in which distance means that the seat\'s distance to its cloest seat(which already be taken), and pos means the seat\'s po
The basic idea is we build a tree set<distance, pos> in which distance means that the seat\'s distance to its cloest seat(which already be taken), and pos means the seat\'s position. When we insert a seat what we should do is add 2 new candidate seat in to the tree. When we remove a seat what we should do is remove 2 candidate seat and add 1 candidate seat. Quiet complex? Let me use an example to illustrate:\nif N = 10 and 0, 9 already be taken, the tree should have (4, 4) \nthen we request a seat, we return 4 and the content in the tree should be change to (2, 2), (2, 6)\nthen we leave 4, we should remove (2, 2) and (2, 6) then we put (4, 4) into the tree\nThere are quit a lot conner case so the code is long, be patient please~\n```\nclass compare{\npublic:\n    bool operator()(pair<int, int> p1, pair<int, int> p2){\n        if(p1.first != p2.first){\n            return p1.first > p2.first;\n        }\n        \n        return p1.second < p2.second;\n    }\n};\n\nclass ExamRoom {\npublic:\n    set<pair<int, int>, compare> s;\n    set<int> taken;\n    int n;\n    \n    ExamRoom(int N) {\n        pair<int, int> first(N, 0);\n        s.insert(first);\n        n = N;\n    }\n    \n    int seat() {\n        auto it = s.begin();\n        int result = it -> second;\n        s.erase(it);\n        \n        auto lower = taken.lower_bound(result);\n        auto higher = taken.upper_bound(result);\n        if(lower != taken.begin()){\n            lower--;\n            int left = *lower;\n            int cur_pos = (result + left) >> 1;\n            if(cur_pos != left){\n                int cur_dist = cur_pos - left;\n                pair<int, int> new_p(cur_dist, cur_pos);\n                s.insert(new_p);\n            }\n        }\n        else{\n            if(result != 0){\n                int cur_pos = 0;\n                int cur_dist = result;\n                pair<int, int> new_p(cur_dist, cur_pos);\n                s.insert(new_p);\n            }\n        }\n        \n        if(higher != taken.end()){\n            int right = *higher;\n            int cur_pos = (right + result) >> 1;\n            if(cur_pos != result){\n                int cur_dist = cur_pos - result;\n                pair<int, int> new_p(cur_dist, cur_pos);\n                s.insert(new_p);\n            }\n        }\n        else{\n            if(result != n - 1){\n                int cur_pos = n - 1;\n                int cur_dist = cur_pos - result;\n                pair<int, int> new_p(cur_dist, cur_pos);\n                s.insert(new_p);\n            }\n        }\n        \n        taken.insert(result);\n        \n        return result;\n    }\n    \n    void leave(int p) {\n        taken.erase(p);\n        auto lower = taken.lower_bound(p);\n        auto higher = taken.upper_bound(p);\n        \n        \n        if(lower != taken.begin()){\n            lower--;\n            int left = *lower;\n            int cur_pos = (p + left) >> 1;\n            if(cur_pos != left){\n                int cur_dist = cur_pos - left;\n                pair<int, int> new_p(cur_dist, cur_pos);\n                s.erase(new_p);\n            }\n            lower++;\n        }\n        else{\n            if(p != 0){\n                int cur_pos = 0;\n                int cur_dist = p;\n                pair<int, int> new_p(cur_dist, cur_pos);\n                s.erase(new_p);\n            }\n        }\n        \n        if(higher != taken.end()){\n            int right = *higher;\n            int cur_pos = (right + p) >> 1;\n            if(cur_pos != p){\n                int cur_dist = cur_pos - p;\n                pair<int, int> new_p(cur_dist, cur_pos);\n                s.erase(new_p);\n            }\n        }\n        else{\n            if(p != n - 1){\n                int cur_pos = n - 1;\n                int cur_dist = cur_pos - p;\n                pair<int, int> new_p(cur_dist, cur_pos);\n                s.erase(new_p);\n            }\n        }\n        \n        if(taken.size() == 0){\n            pair<int, int> first(n, 0);\n            s.insert(first);\n            return;\n        }\n        \n        if(lower == taken.begin()){\n            int right = *higher;\n            int cur_pos = 0;\n            int cur_dist = right;\n            pair<int, int> new_p(cur_dist, cur_pos);\n            s.insert(new_p);\n            return;\n        }\n        \n        if(higher == taken.end()){\n            int left = *lower;\n            int cur_pos = n - 1;\n            int cur_dist = cur_pos - left;\n            pair<int, int> new_p(cur_dist, cur_pos);\n            s.insert(new_p);\n            return;\n        }\n        \n        lower--;\n        int left = *lower;\n        int right = *higher;\n        int cur_pos = (left + right) >> 1;\n        int cur_dist = cur_pos - left;\n        pair<int, int> new_p(cur_dist, cur_pos);\n        // cout << taken.size() << endl;\n        // cout << left << "," << right;\n        s.insert(new_p);\n    }\n};\n```\n 
[]