Fully Explained: Python Fast O(log occupied) seat and leave
Background\n Describe your first thoughts on how to solve this problem. \n- This problem is similar to 849. Maximize Distance to Closest Person but with some di
# Background\n<!-- Describe your first thoughts on how to solve this problem. -->\n- This problem is similar to [849. Maximize Distance to Closest Person](https://leetcode.com/problems/maximize-distance-to-closest-person/description/) but with some differences:\n\n    1. input comes in a stream instead of a single input\n    2. new function `leave`\n\n    So I knew that cases of left/right boundary should be should be handled with extra care.\n\n- Name `S` as the number of occupied seats, `S<n`.\n- `Gap`: Call a sequence of vacant seat with two occupied seats a `Gap`, represented by a 3-tuple (AKA, triplet).\n\n# Intuition\n\n1. We can add new gaps on `seat`, but to do this, we need to pop a current longest `Gap` hence it\'s natural to use a priority queue, because it takes only `O(log l)` time to pop or insert. Due to (3.) we also remove any outdated and invalid gaps that are longer than the valid one.\n2. After having the current longest gap, let\'s deduce the new gap(s) and return the new seat index.\n    - if the gap touches the left boundary, the new seat index is 0, and there\'s no gap on the left, unless the current longest gap also touches the right boundary; \n    - if the gap touches the right boundary, the new seat index is `n-1`, and we cannot add any gap on the left (we can move "unless" here).\n    - otherwise it\'s in the middle, we split the old longest gap into two new gaps.\n3. On `leave` we add a merged big gap, but not removing the old ones: finding it requires going through the entire queue, which takes much longer than doing it in `seat` \n\n\n# Approach\n- We define gap_length as the absolute difference between the indices of two adjacent seats, i.e., `gap_length := abs(seat_1_index - seat_2_index)`. You can subtract or add 1 based if you prefer, as the order doesn\'t change. I used this because mathematically distance == 0 `<=>` seat_1 == seat_2.\n- About `distance`: the `gap_length//2` is a must since we want the "closest person" and since the seats in the classroom are discrete. Also we need `gap_length-1` in the on-boundary cases because we used index `-1` and `n` as sentinel seats.\n- In `Gap`, use `-distance` (negative) to sort the priority queue in descending order. The index of left seat goes the second in `Gap` tuples, to easily achieve "If there are multiple such seats, they sit in the seat with the lowest number"\n- Used a dictionary instead of `SortedList` to store the previous and next seats. It\'s faster tho takes roughly 3x more memory (asymptotically on large room size `n`).\n- Priority queue with `heapq`\n\n# Complexity\n- Time complexity: O(log S) on each `seat` / `leave`\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n\n- Possible improvement: don\'t add gap with length 0. This happens only when `new_seat==l==r-1`. I didn\'t add the `if l==r-1: return` to `__push_gap()`, but those 0-length gap will never be removed from the queue and would possibly use up all memory on large scale of problem!\n\n# Code\n```\n# Similar to [849] Maximize Distance to Closest Person\n# We need a data structure to store the vacancy intervals that can be\n# queried by left, right and ordered by a custom length (when at boundary)\n# With priority queue, we can get the interval with the longest length in\n# O(log n) time but remove is O(n) time.\n# With BBST, we can get the interval with the longest length in\n# O(log n) time and remove is O(log n) time. So I didn\'t finish the pq version.\n# For a flatten BBST, although two lists can be used to store the left ends and\n# right ends, but it\'s longer than just using a occupancy list.\n\n\nfrom heapq import heappop, heappush\n\nGap = tuple[int, int, int]  # -length, left seat index, right seat index\n\n\nclass ExamRoom:\n    def __init__(self, n: int):\n        self.n = n\n        self.ss = {  # seats, to find and edit prev and next seats\n            -1: [None, n],\n            n: [-1, None],\n        }  # sorted list is 3x smaller, but O(log n) slower\n        self.pq: list[Gap] = [(-(n - (-1)), -1, n)]\n\n    def __is_outdated_gap(self, gap: Gap):\n        # we only remove invalid gaps on the fly. otherwise it\'s slower.\n        nn = [None, None]\n        return (\n            # left seat\'s right neighbor is not right seat\n            self.ss.get(gap[1], nn)[1] != gap[2]\n            # or right seat\'s left neighbor is not left seat\n            or gap[1] != self.ss.get(gap[2], nn)[0]\n        )\n\n    def __rm_outdated_gaps(self):\n        # remove outdated gaps\n        while self.pq and self.__is_outdated_gap(self.pq[0]):\n            heappop(self.pq)\n\n    def __push_gap(self, l: int, r: int) -> None:\n        dist = r - l\n        dist = dist - 1 if (l == -1 or r == self.n) else dist // 2\n        heappush(self.pq, (-dist, l, r))\n\n    def seat(self) -> int:\n        self.__rm_outdated_gaps()  # remove outdated gaps\n        _, l, r = heappop(self.pq)  # best valid gap. also sorted by `l` on tie\n        alb, arb = l == -1, r == self.n  # at left boundary, at right boundary\n        ns = 0 if alb else r - 1 if arb else (l + r) // 2  # new seat\n\n        if not alb:  # push a new left gap if not at left boundary\n            self.__push_gap(l, ns)\n        if not arb or alb:  # push a right gap if not at right boundary or alb\n            self.__push_gap(ns, r)\n\n        # curate the seats info\n        self.ss[l][1], self.ss[r][0] = ns, ns\n        self.ss[ns] = [l, r]\n\n        return ns\n\n    def leave(self, p: int) -> None:\n        ss, (prv, nxt) = self.ss, self.ss[p]\n\n        self.__push_gap(prv, nxt)  # push merged adjacent gap. keep the old ones\n\n        # curate the seats info\n        ss[prv][1], ss[nxt][0] = nxt, prv\n        ss.pop(p)\n\n\n# Your ExamRoom object will be instantiated and called as such:\n# obj = ExamRoom(n)\n# param_1 = obj.seat()\n# obj.leave(p)\n```
['Python3']