Naive Approach

A brute force solution would involve iterating through each request and simulating the server assignment process as described in the problem statement. For each request, we'd check the availability of servers starting from (i % k) and wrapping around until an available server is found. If all servers are busy, the request is dropped. We'd maintain a count of requests handled by each server and, at the end, identify the busiest servers.

Code (Python):

def busiest_servers_naive(k, arrival, load):
    servers = [0] * k  # 0 indicates available, time indicates busy until
    counts = [0] * k
    
    for i in range(len(arrival)):
        start_server = i % k
        assigned = False
        
        for j in range(k):
            server_index = (start_server + j) % k
            if servers[server_index] <= arrival[i]:
                servers[server_index] = arrival[i] + load[i]
                counts[server_index] += 1
                assigned = True
                break
                
        if not assigned:
            pass #request dropped
            
    max_count = max(counts)
    busiest = [i for i, count in enumerate(counts) if count == max_count]
    return busiest

Time Complexity: O(n*k), where n is the number of requests (length of arrival) and k is the number of servers.

Space Complexity: O(k), for the servers and counts arrays.

Optimal Approach

To optimize, we can use a priority queue (min-heap) to keep track of available servers and their indices. We also use a sorted set to store the indices of servers that are currently processing requests and will become available in the future.

1. Available Servers: A min-heap will store the indices of the available servers. When a server becomes available, its index is added to the heap. This allows us to quickly find the next available server after the "ideal" i % k server.
2. Busy Servers: We use a sorted set to keep track of when servers will become free. This allows us to efficiently determine what servers have completed their tasks and are once again free for incoming requests.
3. Server Selection: For each request, try to assign it to the server i % k. If that server is available (its index is at the top of the min-heap), assign the task to it. If not, poll the available servers until we find one >= i % k. If we reach the end, start at 0. If the available servers is empty, drop the request.

Code (Python):

import heapq
from sortedcontainers import SortedSet

def busiest_servers(k, arrival, load):
    available = list(range(k))
    heapq.heapify(available)
    busy = SortedSet()
    counts = [0] * k

    for i in range(len(arrival)):
        while busy and busy[0][0] <= arrival[i]:
            _, server_index = busy.pop(0)
            heapq.heappush(available, server_index)

        if not available:
            continue

        start_server = i % k
        
        # Find the next available server index >= start_server
        server_index = -1
        temp_available = []
        while available:
            s = heapq.heappop(available)
            if s >= start_server:
                server_index = s
                break
            else:
                temp_available.append(s)
        
        # If no available server found >= start_server, take the smallest
        if server_index == -1:
            if temp_available:
                server_index = temp_available.pop(0)
            else:
                continue #no available server
                
        for s in temp_available:
            heapq.heappush(available, s)

        counts[server_index] += 1
        busy.add((arrival[i] + load[i], server_index))

    max_count = max(counts)
    busiest = [i for i, count in enumerate(counts) if count == max_count]
    return busiest

Time Complexity: O(n log k), where n is the number of requests and k is the number of servers. The heapq.heappush and heapq.heappop operations take O(log k) time, and in the worst case, we might perform these operations for each request.

Space Complexity: O(k), for the available, busy, and counts arrays.

Edge Cases

• All servers are busy: The code handles the case where all servers are busy by dropping the request and continuing to the next request.
• Large arrival and load values: The code uses integers to store arrival and load times, which should be sufficient for the given constraints (up to 10⁹).
• k = 1: If there is only one server, the modulo operation will always result in 0, so every request is assigned to the same server if it's available.
• Empty arrival/load arrays: The problem statement says the arrays have at least length 1, so we do not need to handle this.