[Python3] heap & hash table
\n\nclass ExamRoom:\n\n    def __init__(self, n: int):\n        self.n = n\n        self.pq = [(-n, -1, n)]\n        self.nei = {-1: [None, n], n: [-1, None]} #
\n```\nclass ExamRoom:\n\n    def __init__(self, n: int):\n        self.n = n\n        self.pq = [(-n, -1, n)]\n        self.nei = {-1: [None, n], n: [-1, None]} # dummy head & tail \n\n    def seat(self) -> int:\n        while self.nei.get(self.pq[0][1], [None]*2)[1] != self.pq[0][2] or self.pq[0][1] != self.nei.get(self.pq[0][2], [None]*2)[0]: heappop(self.pq)\n        _, lo, hi = heappop(self.pq)\n        if lo == -1: \n            x = 0 \n            if hi == self.n: heappush(self.pq, (1-hi, x, hi))\n            else: heappush(self.pq, ((x-hi+1)//2, x, hi))\n        elif hi == self.n: \n            x = self.n-1\n            heappush(self.pq, ((lo-x+1)//2, lo, x))\n        else: \n            x = (lo + hi)//2\n            heappush(self.pq, ((lo-x+1)//2, lo, x))\n            heappush(self.pq, ((x-hi+1)//2, x, hi))\n        self.nei[x] = [lo, hi]\n        self.nei[lo][1] = self.nei[hi][0] = x\n        return x\n\n    def leave(self, p: int) -> None:\n        if self.nei[p][0] == -1: \n            heappush(self.pq, (-self.nei[p][1], -1, self.nei[p][1]))\n        elif self.nei[p][1] == self.n: \n            heappush(self.pq, (-self.n+1+self.nei[p][0], self.nei[p][0], self.n))\n        else: \n            heappush(self.pq, ((self.nei[p][0] - self.nei[p][1] + 1)//2, self.nei[p][0], self.nei[p][1]))\n        self.nei[self.nei[p][0]][1] = self.nei[p][1]\n        self.nei[self.nei[p][1]][0] = self.nei[p][0]\n        self.nei.pop(p)\n```
['Python3']