Elegant O(LogN) C++ solution with set and map
\nstruct Interval {\n    Interval(int _left, int _right, int _n) \n        : left(_left), \n          right(_right), \n          N(_n) {\n        \n    }   \n  
```\nstruct Interval {\n    Interval(int _left, int _right, int _n) \n        : left(_left), \n          right(_right), \n          N(_n) {\n        \n    }   \n    \n    int get_minimax() const {\n        return (left<0) ? ((right < 0) ? N - 1 : right) \n                        : ((right < 0) ? N - 1 - left \n                                       : (right - left) / 2);\n    }\n    \n    int get_mid() const {\n        return (left<0) ? 0 : left + get_minimax();\n    }\n    \n    int left;\n    int right;\n    int N;\n};\n\nbool operator<(const Interval& l, const Interval& r) {\n    \n    int l_minimax = l.get_minimax();\n    int r_minimax = r.get_minimax();\n\n    int l_mid = l.get_mid();\n    int r_mid = r.get_mid();\n    \n    if (l_minimax < r_minimax) return true;\n    if (l_minimax == r_minimax && l_mid > r_mid) return true;\n    return false;\n}\n\nclass ExamRoom {\npublic:\n    ExamRoom(int _n) : N(_n) {\n        Interval first(-1, -1, N);\n        m.insert(first);\n    }\n            \n    int seat() {\n                                           \n        Interval it = (*m.rbegin());\n                \n        int p = it.get_mid();    \n        \n        tail[it.left] = p;\n        head[it.right] = p;\n        \n        tail[p] = it.right;\n        head[p] = it.left;\n        \n        Interval half_left(it.left, p, N);\n        \n        Interval half_right(p, it.right, N);   \n        \n        m.erase(it);\n        m.insert(half_left);\n        m.insert(half_right);\n        \n        return p;\n    }\n    \n    void leave(int p) {\n\n        int old_head = head[p];        \n        m.erase(Interval(old_head, p, N));\n        \n        int old_tail = tail[p];\n        m.erase(Interval(p, old_tail, N));\n        \n        m.insert(Interval(old_head, old_tail, N));\n    }\n    \n    int N;\n    \n    set<Interval> m;\n    unordered_map<int, int> head;\n    unordered_map<int, int> tail;\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```
[]