C++ O(logn) seat() and O(logn) leave() with STL set and map
Much similar to the solution of @spatar, but my solution uses set rather than priority_queue to achieve exactly O(logn) seat() instead of potentially calling he
Much similar to the solution of [@spatar](https://leetcode.com/problems/exam-room/discuss/139941/Python-O(log-n)-time-for-both-seat()-and-leave()-with-heapq-and-dicts-Detailed-explanation), but my solution uses **set** rather than **priority_queue** to achieve exactly O(logn) seat() instead of potentially calling heappop() many times when calling seat() in spatar\'s solution.\n\nLike *Available segment* in spatar\'s solution, I choose *Interval* to indicate which seats are vacant, and implement it in **struct IntV**. My IntV has a static member called **N**, meaning there are N seats in total. I number these seats from 0 to N - 1, consistent with the result of test cases. IntV has two members named **l** and **r**, denoting that all seats in the interval \\[l, r\\] are empty, and either **l == 0** or the seat **l - 1** is taken, as well as either **r == N - 1** or the seat **r + 1** is taken. According to the definition of **interval** here, we can see no two intervals will intersect during the whole process of seating or leaving of students. Struct IntV needs three useful functions as described bellow:\n\n* **getD()**: Say we have an interval \\[l, r\\], this function returns the maximal distance to the closest person a student can achieve when he sits in one of the seats in this interval.\n* **getP()**: Like getD(), but this function returns the seat\'s number that student chooses to sit which can achieve the maximal distance to the closest person.\n* **operator <**: IntV does operator overloading to determine which interval we consider first: those intervals with greater return value of getD() should go first, and when several intervals share the same return value of getD(), the interval with the smallest left end (**l**) should go first.\n\nThese three functions are easy to implement, according to their descriptions.\n\nThen we turn to face **seat()** and **leave()**. I use a **set** (later on I will give the reason why I don\'t use **priority_queue**) named **tab** to record all intervals we have, and at the very beginning we only have \\[0, N - 1\\], a single interval. When we call **seat()**, we can get the first interval of **tab** by visiting iterator **tab.begin()**, which gives us maximal distance to the closest person currently. Then this interval splits into two smaller intervals (it\'s possible one or two of these smaller intervals have a length of 0, meaning no seats at all), so we need to delete the original interval from **tab** and insert two smaller intervals into **tab**. In case there are intervals with zero length, we can see that those intervals must have **l** > **r**, which will give it the lowest priority compared with other intervals (since nobody can sit there), so the implement of **getD()** will take this case into consideration.\n\nWhen we call **leave(int p)**, this question guarantees to have a student currently sitting in seat number p, so we now need to combine two intervals together to make a larger one. The question is: how could we know what these two intervals are? More precisely, among all intervals now in **tab**, we know there is a interval whose **r** is **p - 1**, what\'s its **l**? And there is a interval whose **l** is **p + 1**, what\'s its **r**? This requires us to have two **map**s called **l2r** and **r2l** to record the intervals currently in **tab**, so once we have a left end of a intervals, we can get the interval\'s right end by visiting **l2r**, and the same with **r2l**. So we know what these two interval are, one to the left of **p** and another to the right of **p**, and combine them together to have a larger interval. Then we delete these two smaller intervals from **tab** and insert the larger one. Since here we delete two certain elements from a **set**, it\'s much faster and more convenient than deleting them in **priority_queue**. The **l2r** and **r2l** will change according to the implement of **seat()** and **leave()**; \n\n```\nstruct IntV\n{\n    static int N;\n    int l, r;\n    IntV(int l, int r) : l(l), r(r) {}\n    int getD() const\n    {\n        if(l == 0) return r;\n        if(r == N - 1) return N - 1 - l;\n        if(r < l) return -1;\n        else return (r - l) / 2;\n    }\n    int getP() const\n    {\n        if(l == 0) return 0;\n        if(r == N - 1) return N - 1;\n        else return l + (r - l) / 2;\n    }\n    bool operator < (const IntV& a) const\n    {\n        int d1 = getD(), d2 = a.getD();\n        if(d1 != d2) return d1 > d2;\n        return l < a.l;\n    }\n};\n\nint IntV :: N = 0;\n\nclass ExamRoom {\npublic:\n    set<IntV> tab;\n    map<int, int> l2r, r2l;\n    \n    ExamRoom(int N)\n    {\n        IntV :: N = N;\n        tab.clear(); l2r.clear(); r2l.clear();\n        tab.insert(IntV(0, N - 1));\n        l2r[0] = N - 1;\n        r2l[N - 1] = 0;\n    }\n    \n    int seat()\n    {\n        IntV cur = *(tab.begin());\n        tab.erase(tab.begin());\n        \n        int pos = cur.getP();\n        tab.insert(IntV(cur.l, pos - 1));\n        tab.insert(IntV(pos + 1, cur.r));\n        l2r[cur.l] = pos - 1; r2l[pos - 1] = cur.l;\n        l2r[pos + 1] = cur.r; r2l[cur.r] = pos + 1;\n        return pos;\n    }\n    \n    void leave(int p)\n    {\n        int l = r2l[p - 1], r = l2r[p + 1];\n        tab.erase(IntV(l, p - 1));\n        tab.erase(IntV(p + 1, r));\n        tab.insert(IntV(l, r));\n        l2r[l] = r; r2l[r] = l;\n        r2l.erase(p - 1); l2r.erase(p + 1);\n    }\n};\n```
[]