Python, Two PriorityQueue back and forth O(n log k)
Idea is simple:\n\nUse a priority queue available to keep track of the available servers. When a server get a job, remove it from available and put it in anothe
Idea is simple:\n\nUse a priority queue `available` to keep track of the available servers. When a server get a job, remove it from `available` and put it in another PriorityQueue `busy` whose priority is given by the done time. \n\nOn the arrival each job, check if any of the jobs in `busy` are done. If so, put them back in `available` with the **appropriate index**. So when the `i`-th job comes in, `min(available)` is at least `i`, at most `i+k-1`.\n\nNote that the length of `available` and `busy` are at most `k`. So the heaps are not too big and the complexity is O(n log k) -- every job goes in the priority queue `busy` once, goes out at most once, and when it goes out it go into `available` once.\n\nShort annotated version:\n```\nclass Solution:\n    def busiestServers(self, k: int, A: List[int], B: List[int]) -> List[int]:\n        available = list(range(k)) # already a min-heap\n        busy = [] \n        res = [0] * k\n        for i, a in enumerate(A):\n            while busy and busy[0][0] <= a: # these are done, put them back as available\n                _, x = heapq.heappop(busy)\n                heapq.heappush(available, i + (x-i)%k) # invariant: min(available) is at least i, at most i+k-1\n            if available: \n                j = heapq.heappop(available) % k\n                heapq.heappush(busy, (a+B[i],j))\n                res[j] += 1\n        a = max(res)\n        return [i for i in range(k) if res[i] == a]\n```
['Heap (Priority Queue)', 'Python', 'Python3']