```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 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> seats;\n\tvector 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 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 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

Exam Room

Problem Description

Problem Description

Answer Panel