[Python] O(log n) time for both seat() and leave() with heapq and dicts - Detailed explanation
We will name a range of unoccupied seats from i to j an Available segment with first index i and last index j. For each available segment we can say how far the
We will name a range of unoccupied seats from `i` to `j` an *Available segment* with first index `i` and last index `j`. For each available segment we can say how far the "best" seat in this segment is from the closest occupied seat. The number of empty seats in between is **priority** of the segment. The higher the priority the better seat you can get from a segment. For the edge cases when segment starts with index `0` or ends with index `N - 1` priority equals to `segment_size - 1`. For segments in the middle of the row priority can be calculated as `(segment_size - 1) // 2` or `(last - first) // 2`. Please note that two segments of different size may have equal priority. For example, segments with 3 seats and with 4 seats have the same priority "1".\n\n\nWe will use priority queue `self.heap` to store all currently available segments. Python implements `heapq` as **min heap**, so we will use negated priority to keep the best availabe segment on top of the queue. If two segments have equal priority, then the one with lower `first` index is better. Taken this into account, we will store availabale segment in `self.heap` as 4-items list: `[-segment_priority, first_index_of_segment, last_index_of_segment, is_valid]`. The first two items `-segment_priority` and `first_index_of_segment` guarantee correct priority queue order.\n\n\nA helper function `put_segment()` takes `first` and `last` index of the available segment, calculates its priority and pushes a list object into `self.heap`. In addition, it puts this list object into two dicts: `self.avail_first[first] = segment` and `self.avail_last[last] = segment`. These dicts will be used later in `leave()`.\n\n\nWe start with only one available segment [0, N - 1]. When `seat()` is called, we pop best available segment from `self.heap`. If segment\'s `is_valid` flag is `False` then we pop another one, until we get a valid available segment. There are two edge cases when popped segment starts at 0 or ends at N - 1. For these cases we return the edge seat number (0 or N - 1 respectively) and push new segment into `self.heap`. Otherwize, when the popped segment is in the middle of the row, we return its middle seat and create up to two new available segments of smaller size, and push them into `self.heap`.\n\n\nNow, `leave()` implementation is quite interesting. When seat `p` is vacated, we need to check if there are adjacent available segment(s) in the heap, and merge them together with `p`. We use dicts `self.avail_first` and `self.avail_last` to check for adjacent available segments. If these segment(s) are found, they need to be excluded from `self.heap`. Deleting items in `self.heap` will break heap invariant and requires subsequent `heapify()` call that executes in O(n log n) time. Instead we can just mark segments as invalid by setting `is_valid` flag: `segment[3] = False`. Invalid segments will be skipped upon `heappop()` in `seat()`.\n\n\n```python\nfrom heapq import heappop, heappush\n\n\nclass ExamRoom(object):\n\n    def __init__(self, N):\n        """\n        :type N: int\n        """\n        self.N = N\n        self.heap = []\n        self.avail_first = {}\n        self.avail_last = {}\n        self.put_segment(0, self.N - 1)\n\n    def put_segment(self, first, last):\n\n        if first == 0 or last == self.N - 1:\n            priority = last - first\n        else:\n            priority = (last - first) // 2\n\n        segment = [-priority, first, last, True]\n\n        self.avail_first[first] = segment\n        self.avail_last[last] = segment\n\n        heappush(self.heap, segment)\n\n    def seat(self):\n        """\n        :rtype: int\n        """\n        while True:\n            _, first, last, is_valid = heappop(self.heap)\n\n            if is_valid:\n                del self.avail_first[first]\n                del self.avail_last[last]\n                break\n\n        if first == 0:\n            ret = 0\n            if first != last:\n                self.put_segment(first + 1, last)\n\n        elif last == self.N - 1:\n            ret = last\n            if first != last:\n                self.put_segment(first, last - 1)\n\n        else:\n            ret = first + (last - first) // 2\n\n            if ret > first:\n                self.put_segment(first, ret - 1)\n\n            if ret < last:\n                self.put_segment(ret + 1, last)\n\n        return ret\n\n    def leave(self, p):\n        """\n        :type p: int\n        :rtype: void\n        """\n        first = p\n        last = p\n\n        left = p - 1\n        right = p + 1\n\n        if left >= 0 and left in self.avail_last:\n            segment_left = self.avail_last.pop(left)\n            segment_left[3] = False\n            first = segment_left[1]\n\n        if right < self.N and right in self.avail_first:\n            segment_right = self.avail_first.pop(right)\n            segment_right[3] = False\n            last = segment_right[2]\n\n        self.put_segment(first, last)\n```
[]