Python 3: 2x Slower than Fastest, but No Clever: Find First Server with a Segment Tree
Intuition\n\nWe need to quickly get the earliest available server, if any, in [i%k..k). If none of those are available, get the first available in [0, i%k-1]\n\
# Intuition\n\nWe need to quickly get the earliest available server, if any, in `[i%k..k)`. If none of those are available, get the first available in `[0, i%k-1]`\n\nWhen you see "find the minimum value in a range," you can use a segment tree. In this case:\n* `s -> s` if server `s` in `[0, k)` is available\n* `s -> k` if `s` is not available\n\nWe also need to update the segment tree when servers become available again. The classic way to do these kinds of scheduling problems is to use a min heap:\n* when server `s` becomes busy until `t_end`, push `(t_end, s)` to a heap. Python\'s `heapq` module implements min heaps so it will be ordered earliest "next available time" to latest\n* for each next request time `t`:\n  * while the heap is nonempty, and the min time `<= t`: a server becomes available, so mark it available\n\nIn situations where the range of times is small, it\'s faster to store a list of servers that become available at each time. But the times can be as high as 1e9 so we\'d get MLE if we tried that here.\n\n# Approach\n\nSegment trees sound scary, but they\'re not actually that bad. The code I wrote implements one.\n\nThe scarier version is if you need range updates, then you have to propagate range updates and queries downward to handle "lazy updates," crucial for `O(log(n))` performance.\n\nThe heap stuff is standard.\n\n# Compared to the Clever Solution\n\nThis is slower, range queries involve ascending two pointers whereas maintaining heap invariants involves sifting along one pointer. So the clever solution is definitely faster.\n\nBut I personally would never have gotten the insight that you can enqueue servers as `s + m*k >= i` with the minimum `m`. It definitely works, it\'s just hard IMO to even come up with that quickly in an interview, let alone prove that there won\'t be any nasty edge cases.\n\nSo this one IMO is more reliable in that you don\'t need tricks - "just" the memorization of a range tree instead. But once you understand what the range tree code is doing it\'s quite easy to remember:\n* the `getMin` finds the minimum over `[lo, hi)` within the loop\n* actual values (leaves) are at `i+k`\n* if `lo & 1`, `lo` is the right child. We need ans to reflect this leaf, and we do *not* want to include the whole parent when we ascend to the prior level of the tree because we just want this right child. So we\n  * include `tree[lo]` in the answer\n  * then do `lo += 1` to move it over one: to the left child of the next parent\n  * `lo & 1 == 1` so `lo` ends with a 1 in binary, i.e. `<parent>1`\n  * `lo + 1` therefore toggles the trailing 1 to 0, making it a left child, and the carry will add one to `<parent>`\n  * this way we won\'t ascend to the current parent and risk taking the min over both leaves when we only wanted the right leaf\n* if `hi & 1`, that means the last value we want, `hi-1` is the left child. Following the same logic as `lo & 1`, we want to include only the left child in the range minimum. So include `hi-1` in the minimum\n  * unlike `lo += 1`, `hi` is odd, so subtracting one doesn\'t change the parent\n  * this works because `hi` is exclusive, so after taking the parent\'s left child and ascending, we indeed don\'t want to include *anything* from parent going forward. We already included just the left child as needed\n\n# Complexity\n- Time complexity: `O(N*log(k))` for `N` requests and `k` servers\n\n- Space complexity: `O(k)` for a server heap and segment tree\n\n# Code\n```\nclass Solution:\n    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:\n        # k is 1e5\n        # arrival and load are 1e5 long\n        # arrival andload values are 1e9\n\n        # when request i arrives (arrival is strictly asc)\n        #   > if all servers are busy, drop request\n        #   > elif i % k is available, schedule it\n        #   > else schedule on earliest server in i+1...k-1 then 0..i-1\n        # return the IDs of the servers with max number of requests\n\n        # record if each server is available or not\n        # need fast way to get earliest server available *after* i%k - range min, k as dummy value for if avail or not\n        # \n\n        tasks = [0]*k\n        ready = [] # min heap of (readyAgainTime, serverIndex)\n        lows = [0]*(2*k) # segment tree: min ready index over a range of indices, k means "there\'s no ready server"\n        for i in range(k): lows[i+k] = i\n        for i in range(k-1, 0, -1): lows[i] = min(lows[2*i], lows[2*i+1])\n        \n        def update(i: int, v: int) -> None:\n            lows[i+k] = v\n            i = (i+k)//2\n            while i and lows[i] != (nl := min(lows[2*i], lows[2*i+1])):\n                lows[i] = nl\n                i >>= 1\n\n        def getMin(lo: int, hi: int) -> int:\n            """Min avail server index among [lo, hi]"""\n            lo += k\n            hi += k+1\n            ans = lows[lo]\n            while lo < hi:\n                if lo & 1:\n                    ans = min(ans, lows[lo])\n                    lo += 1\n                if hi & 1:\n                    ans = min(ans, lows[hi-1])\n                lo >>= 1\n                hi >>= 1\n            return ans\n\n        for i, (t, l) in enumerate(zip(arrival, load)):\n            # print(f"{i=}: {t=}, {l=}")\n            while ready and ready[0][0] <= t:\n                _, s = heappop(ready)\n                update(s, s) # mark server s as ready again: s -> s (as opposed to s -> k)\n\n            if len(ready) == k: \n                # print(f"  all servers busy. Next available is {ready[0][1]} at {ready[0][0]}")\n                continue # all servers busy\n\n            s = i % k\n            if lows[s+k] == s:\n                # print(f"  {s=} (i%k) is available, scheduling it there")\n                # server s == i % k is available\n                heappush(ready, (t+l, s)) # s will be ready again at t+l\n                update(s, k) # set s to dummy val so range min is k to indicate "there\'s no server in this range"\n                tasks[s] += 1\n            else:\n                # s isn\'t available, get first avail in s+1..k-1 first, then 0..s-1\n                f = getMin(s+1, k-1) if s < k-1 else k\n                if f == k: f = getMin(0, s-1)\n                # print(f"  {s=} unavailable. Scheduling on next server {f=}")\n\n                heappush(ready, (t+l, f))\n                update(f, k)\n                tasks[f] += 1\n\n        most = max(tasks)\n        return list(s for s, t in enumerate(tasks) if t == most)\n        \n```
['Python3']