Sponsored
Sponsored
This approach involves using a priority queue to manage and track the times when servers become available. Specifically, we will use a heap data structure to efficiently find the first available server for a new request. Whenever a request ends, we reassign the server for future tasks. We also utilize a balanced data structure to cycle through the server indexes and track the server with the most handled requests efficiently.
Time complexity: O(n log k), where n is the number of requests, due to the heap operations. Space complexity: O(k + n) for the heaps and request count.
1import heapq
2from collections import defaultdict
3
4class Solution:
5 def busiestServers(self, k, arrival, load):
6 available = list(range(k))
7 busy = [] # Min-heap for busy servers [(end_time, server_index)]
8 request_count = defaultdict(int)
9 max_requests = 0
10
11 for i, time in enumerate(arrival):
12 # Release servers that have completed their tasks
13 while busy and busy[0][0] <= time:
14 end_time, server = heapq.heappop(busy)
15 heapq.heappush(available, server)
16
17 if not available: # All servers are busy
18 continue
19
20 index = i % k
21 pos = 0
22 if available and available[0] < index:
23 pos = len(available)
24
25 # Find next available server
26 while pos < len(available) and available[pos] < index:
27 pos += 1
28 if pos == len(available):
29 pos = 0
30
31 server = available[pos]
32 heapq.heappop(available)
33 request_count[server] += 1
34 max_requests = max(max_requests, request_count[server])
35 heapq.heappush(busy, (time + load[i], server))
36
37 return [server for server in range(k) if request_count[server] == max_requests]In this code, a min-heap is used to keep track of busy servers and their availability times. Servers that are free are maintained in another heap. For each arriving request, we check if there are available servers that can handle the request.
The modulo operator is used to determine the target server for each request. If the server is not available, we find the next available server using binary search over the heap structure.