O(log n) for both seat and leave, but it is harder than most hard problems
Idea: use a heap to maintain the vacant segment, but there are so many tricky things to handle.\n\n\nclass Segment:\n    def __init__(self, MAX, start, end):\n 
Idea: use a heap to maintain the vacant segment, but there are so many tricky things to handle.\n\n```\nclass Segment:\n    def __init__(self, MAX, start, end):\n        self.MAX = MAX # the most right spot\n        self.start = start\n        self.end = end\n        self.status = True\n    \n    @property\n    def length(self):\n        span = self.end - self.start + 1\n        \n        if self.start == 0 or self.end == self.MAX:\n            return span - 1\n        \n        if span % 2:\n            return span // 2\n        \n        return span // 2 - 1\n\n    \n    def split(self):\n        left = None\n        right = None\n        \n        if self.start == 0:\n            seat = 0    \n        elif self.end == self.MAX:\n            seat = self.MAX\n        else:\n            seat = (self.start + self.end) // 2\n            \n        if seat > self.start:\n            left = Segment(self.MAX, self.start, seat - 1)\n            \n        if seat < self.end:\n            right = Segment(self.MAX, seat + 1, self.end)\n\n        return left, right, seat\n    \n    def __lt__(self, other): # high priority lower\n        if self.length == other.length:\n            return self.start <= other.start \n        \n        return self.length > other.length\n            \n        \nclass ExamRoom:\n\n    def __init__(self, N: int):\n        self.N = N\n        self.MAX = N-1 # the most right spot\n        init_seg = Segment(self.MAX, 0, self.MAX)\n        self.heap = [init_seg]\n        self.seated = {\n            -1: [None, init_seg],\n            N: [init_seg, None]\n        }\n\n    def seat(self) -> int:\n        if len(self.seated) == self.N + 2: # -1, and N are two virtual seat\n            raise Exception(\'Room full, sorry\')\n            \n        seg = self._pop()\n        left, right, seat = seg.split()\n        self._push(left)\n        self._push(right)\n        self.seated[seat] = [left, right]\n        \n        # tricky part\n        self.seated[seg.start-1][1] = left\n        self.seated[seg.end+1][0] = right\n        \n        return seat\n\n    def leave(self, p: int) -> None:\n        if p not in self.seated:\n            raise Exception(\'No person sits there\')\n        \n        left, right = self.seated[p]\n        del self.seated[p]\n        \n        start = p\n        end = p\n        \n        if left:\n            left.status = False\n            start = left.start\n            \n        if right:\n            right.status = False\n            end = right.end\n        \n        merged = Segment(self.MAX, start, end)\n        # tricky part\n        self.seated[merged.start-1][1] = merged\n        self.seated[merged.end+1][0] = merged\n        \n        self._push(merged)\n        \n    \n    def _push(self, seg):\n        if seg:\n            heapq.heappush(self.heap, seg)\n        \n    def _pop(self):\n        while self.heap:\n            seg = heapq.heappop(self.heap)\n            if seg.status: # drop invalid segs\n                return seg\n        \n        raise Exception(\'empty heap\')\n\t\t\n```
[]