Find Servers That Handled Most Number of Requests

Problem Description

You have k servers numbered from 0 to k-1 that are being used to handle multiple requests simultaneously. Each server has infinite computational capacity but cannot handle more than one request at a time. The requests are assigned to servers according to a specific algorithm:

• The ith (0-indexed) request arrives.
• If all servers are busy, the request is dropped (not handled at all).
• If the (i % k)th server is available, assign the request to that server.
• Otherwise, assign the request to the next available server (wrapping around the list of servers and starting from 0 if necessary).

You are given a strictly increasing array arrival of positive integers, where arrival[i] represents the arrival time of the ith request, and another array load, where load[i] represents the load of the ith request (the time it takes to complete). Your goal is to find the busiest server(s). A server is considered busiest if it handled the most number of requests successfully among all the servers.

Return a list containing the IDs (0-indexed) of the busiest server(s). You may return the IDs in any order.

Key Insights

• Each server can only handle one request at a time.
• Requests are assigned based on their arrival time and the server's availability.
• The algorithm wraps around to the start of the server list when searching for an available server.
• A server's busyness can be tracked using its completion time.

Space and Time Complexity

Time Complexity: O(n log k) - where n is the number of requests. This is due to the use of a priority queue to manage server availability. Space Complexity: O(k) - where k is the number of servers, used for tracking their completion times and counts.

Solution

To solve the problem, we can use a priority queue (min-heap) to manage server availability based on their completion times. We also maintain an array to count the number of requests handled by each server. The algorithm proceeds as follows:

1. Initialize a min-heap to keep track of when each server will be free.
2. For each request, check if the server (i % k) is available. If it is, assign the request to it. If not, check the next servers in a circular manner.
3. Update the server's next available time and increment its count of handled requests.
4. After processing all requests, determine the server(s) with the maximum count of handled requests.

Code Solutions