[Python] O(logN) time for both seat() and leave() Using Segment Tree
\nclass SegmentTree(object):\n    def __init__(self, start, end, size, rank=1):\n        self.rank = rank  # rank is the number of leaves of this segment tree, 
```\nclass SegmentTree(object):\n    def __init__(self, start, end, size, rank=1):\n        self.rank = rank  # rank is the number of leaves of this segment tree, to keep the segment tree balance and reduce the depth of the tree\n        self.start = start\n        self.end = end\n        self.left = None\n        self.right = None\n        self.priority_segment = self  # the most priority segment\n        self.priority = end - start if start == 0 or end == size - 1 else (end - start) // 2\n\n\nclass ExamRoom(object):\n\n    def __init__(self, N):\n        """\n        :type N: int\n        """\n        self.segmentTree = SegmentTree(0, N - 1, N)\n        self.N = N\n\n\n    def position(self):\n        node = self.segmentTree.priority_segment\n        if node.start == 0:\n            return 0\n        if node.end == self.N - 1:\n            return self.N - 1\n        return (node.start + node.end) // 2\n\n    def update(self, node):\n        """\n        :type node: SegmentTree\n        :rtype: SegmentTree\n        """\n\t\t# after modifying some node (remove or add or merge seats), update all ancestors nodes\n        if not node or not node.left and not node.right:\n            return node\n        if not node.left or not node.right:\n            return node.left or node.right\n        node.rank = node.left.rank + node.right.rank\n        node.start = node.left.start\n        node.end = node.right.end\n        if node.left.priority >= node.right.priority:\n            node.priority = node.left.priority\n            node.priority_segment = node.left.priority_segment\n        else:\n            node.priority = node.right.priority\n            node.priority_segment = node.right.priority_segment\n        return node\n\n    def remove(self, node, p):\n        """\n        :type node: SegmentTree\n        :type p: int\n        :rtype: SegmentTree\n        """\n\t\t# occupy seat p, and return new segment node\n        if node.end < p or node.start > p:\n            return node\n        if not node.left:\n            if node.start == node.end:\n                return None\n            if p == node.start:\n                return SegmentTree(p + 1, node.end, self.N)\n            if p == node.end:\n                return SegmentTree(node.start, p - 1, self.N)\n            node.left = SegmentTree(node.start, p - 1, self.N)\n            node.right = SegmentTree(p + 1, node.end, self.N)\n        else:\n            node.left = self.remove(node.left, p)\n            node.right = self.remove(node.right, p)\n        return self.update(node)\n\n    def add(self, node, p):\n        """\n        :type node: SegmentTree\n        :type p: int\n        :rtype: SegmentTree\n        """\n\t\t# release seat p\n* \t\t  # # add segment besides leaves, may increase the segment tree\'s depth\n*         # if not node.left:\n*         #     ans = SegmentTree(min(p, node.start), max(p, node.end), self.N)\n*         #     if p == node.start - 1 or p == node.end + 1:\n*         #         return ans\n*         #     cur_node = SegmentTree(p, p, self.N)\n*         #     if p < node.start - 1:\n*         #         ans.left = cur_node\n*         #         ans.right = node\n*         #     else:\n*         #         ans.left = node\n*         #         ans.right = cur_node\n*         #     node = ans\n*         # elif p <= (node.end + node.start) // 2:\n*         #     node.left = self.add(node.left, p)\n*         # else:\n*         #     node.right = self.add(node.right, p)\n*         # if node.left.end + 1 == node.right.start:\n*         #     node.left, node.right = self.merge(node.left, node.right, node.left.rank < node.right.rank)\n*         # return self.update(node)\n        \n\t\t# not always add segment besides leaves\n        if p < node.start - 1 or p > node.end + 1 or not node.left:\n            ans = SegmentTree(min(p, node.start), max(p, node.end), self.N)\n            cur_node = SegmentTree(p, p, self.N)\n            if p < node.start - 1:\n                ans.left = cur_node\n                ans.right = node\n            elif p > node.end + 1:\n                ans.left = node\n                ans.right = cur_node\n            node = ans\n            return self.update(node)\n        elif p <= (node.right.start + node.left.end) // 2:\n            node.left = self.add(node.left, p)\n        else:\n            node.right = self.add(node.right, p)\n\t\t# if adjascent subtrees don\'t have gap between them, merge them\n        if node.left.end + 1 == node.right.start:\n            node.left, node.right = self.merge(node.left, node.right, node.left.rank < node.right.rank)\n        return self.update(node)\n\n    def merge(self, n1, n2, toLeft = True):\n        """\n        :type n1: SegmentTree\n        :type n2: SegmentTree\n        :rtype: SegmentTree, SegmentTree\n        """\n\t\t# if n1.rank < n2.rank, merge to left: delete the first leaf segment of n2, extend the last leaf segment of n1\n\t\t# otherwise, merge to right: delete the last leaf segment of n1, extend the first leaf segment of n2\n        if not n1.left and not n2.left:  # both are leaves\n            if toLeft:\n                return SegmentTree(n1.start, n2.end, self.N), None\n            else:\n                return None, SegmentTree(n1.start, n2.end, self.N)\n        if not n1.left:\n            n1, n2.left = self.merge(n1, n2.left, toLeft)\n        elif not n2.left:\n            n1.right, n2 = self.merge(n1.right, n2, toLeft)\n        else:\n            n1.right, n2.left = self.merge(n1.right, n2.left, toLeft)\n        n1 = self.update(n1)\n        n2 = self.update(n2)\n        return n1, n2\n\n\n    def seat(self):\n        """\n        :rtype: int\n        """\n\t\t# \n        pos = self.position()\n        self.segmentTree = self.remove(self.segmentTree, pos)\n        return pos\n\n\n    def leave(self, p):\n        """\n        :type p: int\n        :rtype: None\n        """\n        if not self.segmentTree:\n            self.segmentTree = SegmentTree(p, p, self.N)\n        else:\n            self.segmentTree = self.add(self.segmentTree, p)\n```
[]