[Python3] summarizing 3 approaches
Approach 1 - heap only \nI was completely amazed to learn this solution from @warmr0bot in this post. Here, the trick is to relocate a freed server to a later p
**Approach 1** - heap only \nI was completely amazed to learn this solution from @warmr0bot in this [post](https://leetcode.com/problems/find-servers-that-handled-most-number-of-requests/discuss/876883/Python-using-only-heaps). Here, the trick is to relocate a freed server to a later place by circularly adjusting its index. In this way, when we are looking server `ii` at position `i` where `ii < i`, we will free `ii` to a place `ii + x*k` where `x` is enough so that `ii+x*k` bearly passes `i`. Mathematically, `i + (ii-i)%k` does the trick. \n\nImplementation \n```\nclass Solution:\n    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:\n        busy = [] # min-heap\n        free = list(range(k)) # min-heap \n        freq = [0]*k\n        \n        for i, (ta, tl) in enumerate(zip(arrival, load)): \n            while busy and busy[0][0] <= ta: \n                _, ii = heappop(busy)\n                heappush(free, i + (ii - i) % k) # circularly relocate it\n            if free: \n                ii = heappop(free) % k \n                freq[ii] += 1\n                heappush(busy, (ta+tl, ii))\n        \n        mx = max(freq)\n        return [i for i, x in enumerate(freq) if x == mx]\n```\n\n**Approach 2** - Fenwick tree\nThis is my original approach, but it is really slow (8000+ms). Here, we use a Fenwick tree to label free servers and use binary search to locate the left-most free servers past a give index `i`. \n\n```\nclass Fenwick: \n\tdef __init__(self, n: int):\n\t\tself.nums = [0]*(n+1)\n\n\tdef sum(self, k: int) -> int: \n\t\t"""Return the sum of nums[:k]."""\n\t\tans = 0\n\t\twhile k:\n\t\t\tans += self.nums[k]\n\t\t\tk -= k & -k # unset last set bit \n\t\treturn ans\n\n\tdef add(self, k: int, x: int) -> None: \n\t\tk += 1\n\t\twhile k < len(self.nums): \n\t\t\tself.nums[k] += x\n\t\t\tk += k & -k \n    \n\nclass Solution:\n    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:\n        freq = [0]*k # counter \n        pq = [] # min-heap \n        \n        fw = Fenwick(k) # count of available servers \n        for i in range(k): fw.add(i, 1) \n        \n        for i, (ta, tl) in enumerate(zip(arrival, load)): \n            i %= k \n            while pq and pq[0][0] <= ta: \n                _, ii = heappop(pq) # release servers \n                fw.add(ii, 1)\n            \n            if fw.sum(k):\n                if fw.sum(k) - fw.sum(i): lo, hi, x = i, k, fw.sum(i)\n                else: lo, hi, x = 0, i, 0\n                \n                while lo < hi: \n                    mid = lo + hi >> 1\n                    if fw.sum(mid) - x: hi = mid\n                    else: lo = mid + 1\n                fw.add(lo-1, -1)\n                freq[lo-1] += 1\n                heappush(pq, (ta+tl, lo-1))\n                \n        mx = max(freq)\n        return [i for i, x in enumerate(freq) if x == mx]\n```\n\n**Approach 3** - SortedList\n`SortedList` is an interesting data structure of `sortedcontainers` which is an external library and doesn\'t come with Python by default. I believe the underlying data structure is a balanced bst. \n\n```\nfrom sortedcontainers import SortedList\n\nclass Solution:\n    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:\n        freq = [0]*k\n        busy = [] # min-heap \n        free = SortedList(range(k)) # balanced bst\n        \n        for i, (ta, tl) in enumerate(zip(arrival, load)): \n            while busy and busy[0][0] <= ta: \n                _, ii = heappop(busy)\n                free.add(ii)\n            \n            if free: \n                ii = free.bisect_left(i%k) % len(free)\n                server = free.pop(ii)\n                freq[server] += 1\n                heappush(busy, (ta+tl, server))\n        \n        mx = max(freq)\n        return [i for i, x in enumerate(freq) if x == mx]\n```
['Python3']