Python - HEAP + SORTED LIST + BINARY SEARCH ✅
APPROACH 1 - TLE\n\nBefore explaining the accepted solution, let me share the solution which I initially wrote and which gave TLE. This solution was passing 105
# **APPROACH 1 - TLE**\n\nBefore explaining the accepted solution, let me share the solution which I initially wrote and which gave TLE. This solution was passing 105/108 test cases.\n\nBasically, if you ignore the condition that says the "i % k" server is the most optimal server for a request "i", then this problem because very simple. Because now, all we need to do is simulate the whole process using two heaps, one will have all the available servers, and the other will have all the busy servers.\n\nAll the available servers will be ordered by their indices from smallest to largest, and the busy servers will be ordered by the time at which they will again be available. And this order will be from smallest to longest time.\n\nSo basically, both these will be MIN HEAPS.\n\nFor every new request that comes at a time "x", we will check if among the busy servers, there are some servers that are now available. That will be the case if the time at which they are available is <= "x". If that is true, we will move them back to the available servers heap.\n\nAnd in this way, we process the requests.\n\nBut then, we have an extra condition in this problem that says for a request "i", the most optimal server that will pick that request is "i % k". If that server is not available, then the next most optimal server is "i % k" + 1 and so on till we reach the last server. If we still cannot find an optimal server, then we will start looking at available servers starting from server 0.\n\nSo, one way can be to maintain a set of available servers so that at any time, we can check if "i%k" is in the set or not. If yes, then good. If not, then we can check if "i % k"+ 1 is in the set or not. And we keep doing it until we reach the end.\n\nAnd if we still cannot find a server, we then simply assign the request to the available server with the smallest index, that is, the top of the MIN HEAP.\n\nBut, this extra step of checking if optimal servers are available or not takes some extra time, and for large test cases, this will result in TLE. We need a more efficient way to find the most optimal server, instead of having to do a linear search.\n\n```\ndef busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:\n        \n        # How many requests are there\n        n = len(arrival)\n        \n        # Initially all the servers are available\n        # So, we will put all the available servers a queue-like data structure\n        # This will order the servers by their indices from smallest to largest\n        # So, it will be a MIN HEAP\n        availableServers = []  \n        \n        # A Set to keep track of the server indices of available servers\n        # So that we can quickly check if i%k server is available or not\n        availableSet = set()\n        \n        # Initially, all servers are available\n        for i in range(k): \n            heappush(availableServers, i)\n            availableSet.add(i)\n        \n        # Another queue-like data structure that will be used to keep track of all the busy servers\n        # This will order the servers by the time at which they will be available again (from smallest to largest)\n        # So, it will be a MIN HEAP\n        busyServers = []\n        \n        # A dictionary to keep track of how many requests each server handled\n        requestCount = {}\n        \n        # We will go over the arrival times from left to right\n        for i in range(n):\n            \n            # First, check if there are servers in the "busyServers"  Min Heap\n            # That should be available by the current arrival time\n            # If yes, then move them back to the available servers list\n            while busyServers and busyServers[0][0] <= arrival[i]: \n                \n                # Index of the server on top of "busyServers" Min Heap\n                idx = heappop(busyServers)[1]\n                \n                # Add the server back to the "availableServers"\n                heappush(availableServers, idx)\n                \n                # Also add the server to the availableServers set\n                availableSet.add(idx)\n                \n                \n            # If the servers on top of the "availableServers" minHeap are not in "availableSet"\n            # Remove them from the minHeap\n            while availableServers and availableServers[0] not in availableSet: heappop(availableServers)\n                \n            # If no servers are available, skip current request\n            if not availableSet: continue\n                \n            reqServer = i % k\n            while reqServer < k and reqServer not in availableSet: reqServer += 1\n            \n            if reqServer in availableSet:\n                heappush(busyServers, [arrival[i] + load[i], reqServer])\n                availableSet.remove(reqServer)\n                requestCount[reqServer] = requestCount.get(reqServer,0) + 1\n            else:\n                idx = heappop(availableServers)\n                heappush(busyServers, [arrival[i] + load[i], idx])\n                availableSet.remove(idx)\n                requestCount[idx] = requestCount.get(idx,0) + 1\n                \n\n        # What is the maximum count of requests handled\n        maxCount = max(requestCount.values())\n\n        # Return all the servers that handles "maxCount" number of requests     \n        return [key for key in requestCount if requestCount[key] == maxCount]\n```\n\n# **APPROACH 2 - SORTED LIST + BINARY SEARCH**\nSince a linear search is not a good approach, a better way is to do a Binary Search.\n\nBut, for Binary Search, the available servers need to be in a Sorted Order. And well, we cannot sort the list of available servers each time a new server gets added. But, we can use something that takes care of sorting. No, it is not a HEAP. It is a "SORTED LIST". Why not a Heap? Because while a Heap will take care of sorting, if we have to remove something from heap that is not on top, the worst case time complexity in that case if O(N). But, if we have a Sorted List, no matter from which index we remove an item, the time complexity is approximately O(LogN).\n\nAnd so, for the available servers, we will use a Sorted List. In this way, there is no way to have an extra set as well.\n\nThe whole logic remains almost the same, except that to find the most optimal server, we use Binary Search.\n\nWe know that for a request "i", the most optimal server is "i % k". If that is not available then it is "i % k" + 1 and so on..\n\nIn simple words, for a request "i", the most optimal server is the one that has an index closest to the "i % k" index. In other words, the leftmost server in the "availableServers" list that has index >= i % k. And well, that\'s exactly what we will find using Binary Search.\n\nIf we cannot find one, it simply means, we can now pick the server with the smallest index in the available servers. That is, the first server in this list (since the list is always in a sorted order).\n\nAnd well, that\'s it. That\'s the whole approach.\n\n```\ndef busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:\n        \n        # How many requests are there\n        n = len(arrival)\n        \n        # We will use a Sorted List to keep track of the available servers and their indices\n        availableServers = SortedList()\n        \n        # Initially, all servers are available\n        for i in range(k): availableServers.add(i)\n        \n        # A queue-like data structure that will be used to keep track of all the busy servers\n        # This will order the servers by the time at which they will be available again (from smallest to largest)\n        # So, it will be a MIN HEAP\n        busyServers = []\n        \n        # A dictionary to keep track of how many requests each server handled\n        requestCount = {}\n        \n        # We will go over the arrival times from left to right\n        for i in range(n):\n            \n            # First, check if there are servers in the "busyServers"  Min Heap\n            # That should be available by the current arrival time\n            # If yes, then move them back to the available servers list\n            while busyServers and busyServers[0][0] <= arrival[i]: \n                \n                # Index of the server on top of "busyServers" Min Heap\n                idx = heappop(busyServers)[1]\n                \n                # Add the server back to the "availableServers" Sorted List\n                availableServers.add(idx)\n                \n            # If no servers are available, drop the current request\n            if not availableServers: continue\n                \n            # Now, for the current request "i", we are looking for the most optimal server\n            # And that server is "i % k"\n            # If "i%k" is not available, we can use "i%k" + 1... and so on till we reach the end\n            # Because if we reach the end, we have to then pick a server from the beginning, if available\n            # So basically, we want the leftmost index of server in our "availableServers" list that is >= i % k\n            # So, we can use Binary Search here since we have a "SORTED LIST"\n            \n            leftmostIndex = -1\n            \n            start,end = 0, len(availableServers) - 1\n            \n            while start <= end:\n                mid = start + (end - start) // 2\n                \n                # Does the server at "mid" have index >= i % k?\n                # If yes, then save it and keep searching on left side of mid\n                if availableServers[mid] >= i % k:\n                    leftmostIndex = mid\n                    end = mid - 1\n                    \n                # Otherwise, look for a server on the right side of mid\n                else: start = mid + 1\n                    \n            # If leftmostIndex is -1 at this point, it means we will have to look at the servers, starting from index 0\n            # That is, we are now wrapping around the list of server starting from 0\n            # And well, since "availableServers" list is already sorted, it means that would be the first server in this list\n            if leftmostIndex == -1: leftmostIndex = 0\n                \n            # The server at "leftmostIndex" will process the current request and so, we push it to the "busyServers" Min Heap\n            idx = availableServers.pop(leftmostIndex)\n            \n            # The time at which it will be available again is -> arrival time + load time\n            heappush(busyServers, [arrival[i] + load[i], idx])\n            \n            # Update the dictionary\n            requestCount[idx] = requestCount.get(idx,0) + 1       \n\n        # What is the maximum count of requests handled\n        maxCount = max(requestCount.values())\n\n        # Return all the servers that handles "maxCount" number of requests     \n        return [key for key in requestCount if requestCount[key] == maxCount]\n```
['Binary Search', 'Heap (Priority Queue)', 'Python']