Python heapq clean solution with explanation, seat O(log n) leave O(n)
seat: O(log n)\nleave: O(n)\n\nThis solution is largely inspired by:\nhttps://leetcode.com/problems/exam-room/discuss/148595/Java-PriorityQueue-with-customized-
seat: `O(log n)`\nleave: `O(n)`\n\nThis solution is largely inspired by:\nhttps://leetcode.com/problems/exam-room/discuss/148595/Java-PriorityQueue-with-customized-object.-seat:-O(logn)-leave-O(n)-with-explanation\n\nwith a few modification to work in Python. A few things I\'ve learned during the process:\n\n1. `heapq` implements a `minheap`, to use a `maxheap`, simpy negate the proirity (x -> -x)\n2. If you want to store the priority together with the data, you can use tuple as the element data structure, e.g. `heapq.heapify([(1, "data")])`\n3. In case there is a tie, you can specify a second priority, if you are using tuple that would be the second item, e.g. `(1, 1, 3) < (1, 2, 2)`\n4. If you remove an item from the underlying list (using either `del` or `.remove`), you have do `heapify` again on the list, otherwise it will lose the heap property.\n\n```python\nclass ExamRoom:\n    \n    def dist(self, x, y):  # length of the interval (x, y)\n        if x == -1:        # note here we negate the value to make it maxheap\n            return -y\n        elif y == self.N:\n            return -(self.N - 1 - x)\n        else:\n            return -(abs(x-y)//2) \n        \n    def __init__(self, N):\n        self.N = N\n        self.pq = [(self.dist(-1, N), -1, N)]  # initialize heap\n        \n    def seat(self):\n        _, x, y = heapq.heappop(self.pq)  # current max interval \n        if x == -1:\n            seat = 0\n        elif y == self.N:\n            seat = self.N - 1\n        else:\n            seat = (x+y) // 2\n        heapq.heappush(self.pq, (self.dist(x, seat), x, seat))  # push two intervals by breaking at seat\n        heapq.heappush(self.pq, (self.dist(seat, y), seat, y))\n        return seat\n        \n    def leave(self, p):\n        head = tail = None\n        for interval in self.pq:  # interval is in the form of (d, x, y)\n            if interval[1] == p:  \n                tail = interval\n            if interval[2] == p:  \n                head = interval\n            if head and tail:\n                break\n        self.pq.remove(head)\n        self.pq.remove(tail)\n\t\theapq.heapify(self.pq)  # important! re-heapify after deletion\n        heapq.heappush(self.pq, (self.dist(head[1], tail[2]), head[1], tail[2]))\n```
[]