Solution
C++ []\nclass ExamRoom {\npublic:\n\tstruct gap_t {\n\t\tint get_best_seat(int n) const {\n\t\t\tif (start == 0) {\n\t\t\t\treturn 0;\n\t\t\t} if (start + size 
```C++ []\nclass ExamRoom {\npublic:\n\tstruct gap_t {\n\t\tint get_best_seat(int n) const {\n\t\t\tif (start == 0) {\n\t\t\t\treturn 0;\n\t\t\t} if (start + size == n) {\n\t\t\t\treturn n - 1;\n\t\t\t} return start + size / 2 - (size % 2 ^ 1);\n\t\t}\n\t\tint max_seat_dist(int n) const {\n\t\t\tif (start == 0) {\n\t\t\t\treturn size - 1;\n\t\t\t} if (start + size == n) {\n\t\t\t\treturn size - 1;\n\t\t\t} return size / 2 - (size % 2 ^ 1);\n\t\t}\n\t\ttuple<gap_t, gap_t> split(int n) const {\n\t\t\tint seat = get_best_seat(n);\n\t\t\treturn {{start, seat - start}, {seat + 1, start + size - seat - 1}};\n\t\t}\n\t\tbool empty() const {\n\t\t\treturn size <= 0;\n\t\t}\n        bool operator == (const gap_t& another) const {\n            return start == another.start && size == another.size;\n        }\n        bool operator != (const gap_t& another) const {\n            return !(*this == another);\n        }\n\t\tint start{};\n\t\tint size{};\n\t};\n\tstruct gap_order_compare_t {\n\t\tbool operator() (const gap_t& g1, const gap_t& g2) const {\n\t\t\treturn g1.start < g2.start;\n\t\t}\n\t};\n\tstruct gap_size_compare_t {\n\t\tbool operator() (const gap_t& g1, const gap_t& g2) const {\n\t\t\tint d1 = g1.max_seat_dist(n);\n            int d2 = g2.max_seat_dist(n);\n            if (d1 != d2) {\n                return d1 < d2;\n            } return g1.start > g2.start;\n\t\t}\n\t\tint n{};\n\t};\n    ExamRoom(int _n) : n{_n} {\n\t\tgaps.push_back({0, n});\n\t\tseats.insert(-1);\n\t\tseats.insert(n);\n\t}\n\tgap_t get_gap(int gap) {\n\t\tauto it = seats.lower_bound(gap);\n\t\tint start = *it + 1;\n\t\t--it;\n\t\tint size = *it - start;\n\t\treturn {start, size};\n\t}\n\tvoid pop_gap() {\n\t\tpop_heap(gaps.begin(), gaps.end(), gap_size_compare_t{n});\n\t\tgaps.pop_back();\n    }\n\tvoid push_gap(const gap_t& gap) {\n\t\tgaps.push_back(gap);\n\t\tpush_heap(gaps.begin(), gaps.end(), gap_size_compare_t{n});\n\t}\n    int seat() {\n\t\twhile (!gaps.empty()) {\n\t\t\tauto gap = gaps.front();\n\t\t\tauto true_gap = get_gap(gap.start);\n\t\t\tpop_gap();\n\t\t\tif (gap != true_gap) {\n\t\t\t\tcontinue;\n\t\t\t}\n\t\t\tint new_seat = gap.get_best_seat(n);\n\t\t\tseats.insert(new_seat);\n\n\t\t\tauto [g1, g2] = gap.split(n);\n\t\t\tif (!g1.empty()) {\n\t\t\t\tpush_gap(g1);\n\t\t\t} if (!g2.empty()) {\n\t\t\t\tpush_gap(g2);\n\t\t\t}\n\t\t\treturn new_seat;\n\t\t} return -1;\n    }\n    void leave(int p) {\n\t\tseats.erase(p);\n\t\tpush_gap(get_gap(p));\n    }\n    int n{};\n\tset<int, greater<int>> seats;\n\tvector<gap_t> gaps;\n};\n```\n\n```Python3 []\nclass ExamRoom:\n\n    def __init__(self, n: int):\n        self.n = n\n        self.heap = []\n\n        self.heap.append((-self.dist(0, n - 1), 0, n - 1))\n\n    def seat(self) -> int:\n        res = 0\n\n        curr_dist, l, r = heappop(self.heap)\n        curr_dist = -curr_dist\n\n        if l == 0:\n            res = 0\n        elif r == self.n - 1:\n            res = self.n - 1\n        else:\n            res = l + curr_dist\n        \n        if res > l:\n            heappush(self.heap, (-self.dist(l, res - 1), l, res - 1))\n        \n        if res < r:\n            heappush(self.heap, (-self.dist(res + 1, r), res + 1, r))\n\n        return res\n\n    def leave(self, p: int) -> None:\n        prev_interval, next_interval = None, None\n\n        for item in self.heap:\n            if item[1] - 1 == p:\n                next_interval = item\n            if item[2] + 1 == p:\n                prev_interval = item\n        \n        start = p\n        end = p\n        if prev_interval:\n            start = prev_interval[1]\n            self.heap.remove(prev_interval)\n        if next_interval:\n            end = next_interval[2]\n            self.heap.remove(next_interval)\n\n        heappush(self.heap, (-self.dist(start, end), start, end))\n        \n    def dist(self, l, r):\n        if l == 0 or r == self.n - 1:\n            return r - l\n        else:\n            return (r - l) // 2\n```\n\n```Java []\nclass ExamRoom {\n\tprivate int n;\n\tprivate Queue<Interval> queue;\n\tpublic ExamRoom(int n) {\n\t\tthis.queue = new PriorityQueue<>((a, b) -> a.length != b.length ? b.length - a.length : a.start - b.start);\n\t\tthis.n = n;\n\t\tthis.queue.offer(new Interval(n, 0, this.n - 1));\n\t}\n\tpublic int seat() {\n\t\tInterval interval = this.queue.poll();\n\t\tint result;\n\t\tif (interval.start == 0) {\n\t\t\tresult = 0;\n\t\t} else if (interval.end == this.n - 1) {\n\t\t\tresult = this.n - 1;\n\t\t} else {\n\t\t\tresult = interval.start + interval.length;\n\t\t}\n\t\tif (result > interval.start) {\n\t\t\tthis.queue.offer(new Interval(n, interval.start, result - 1));\n\t\t}\n\t\tif (result < interval.end) {\n\t\t\tthis.queue.offer(new Interval(n, result + 1, interval.end));\n\t\t}\n\t\treturn result;\n\t}\n\tpublic void leave(int p) {\n\t\tList<Interval> list = new ArrayList<>(this.queue);\n\t\tInterval prev = null;\n\t\tInterval next = null;\n\t\tfor (Interval interval : list) {\n\t\t\tif (interval.end + 1 == p) {\n\t\t\t\tprev = interval;\n\t\t\t}\n\t\t\tif (interval.start - 1 == p) {\n\t\t\t\tnext = interval;\n\t\t\t}\n\t\t}\n\t\tthis.queue.remove(prev);\n\t\tthis.queue.remove(next);\n\t\tthis.queue.offer(new Interval(n, prev == null ? p : prev.start, next == null ? p : next.end));\n\t}\n}\nclass Interval {\n\tint start;\n\tint end;\n\tint length;\n\tpublic Interval(int n, int start, int end) {\n\t\tthis.start = start;\n\t\tthis.end = end;\n\t\tif (start == 0 || end == n - 1) {\n\t\t\tthis.length = end - start;\n\t\t} else {\n\t\t\tthis.length = (end - start) / 2;\n\t\t}\n\t}\n}\n```\n
['C++', 'Java', 'Python3']