Find Servers That Handled Most Number of Requests

class Solution {
public:
    vector<int> matchLoad(int k, vector<int>& arrival, vector<int>& load) {
        vector<int> serverCount(k, 0);
        priority_queue<int, vector<int>, greater<int>> availServers;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> occupiedServers;

        for (int i = 0; i < k; ++i) {
            availServers.push(i);
        }

        for (int i = 0; i < arrival.size(); ++i) {
            int startTime = arrival[i];

            while (!occupiedServers.empty() && occupiedServers.top().first <= startTime) {
                auto [finishTime, serverID] = occupiedServers.top();
                occupiedServers.pop();
                int newID = ((serverID - i) % k + k) % k + i;
                availServers.push(newID);
            }

            if (!availServers.empty()) {
                int assignedID = availServers.top() % k;
                availServers.pop();
                occupiedServers.push({startTime + load[i], assignedID});
                serverCount[assignedID]++;
            }
        }

        vector<int> results;
        int maxLoad = *max_element(serverCount.begin(), serverCount.end());
        for (int i = 0; i < k; ++i) {
            if (serverCount[i] == maxLoad) {
                results.push_back(i);
            }
        }
        
        return results;
    }
};

To identify the servers that processed the most requests, the given C++ solution performs a simulation using priority queues to efficiently manage server availability and task durations.

• The function matchLoad takes three parameters:

  • k denotes the total number of servers.
  • arrival is a vector where each element represents the time a request arrives.
  • load is a vector where each corresponding element represents the duration of the request initiated at the arrival time.

• Maintain two main data structures:

  • serverCount, a vector that tracks the number of requests each server handles.
  • availServers, a priority queue (min-heap) that stores the indices of available servers.
  • occupiedServers, a priority queue (min-heap) that tracks servers currently occupied by requests. It pairs the finish time of a request with the server's index.

• Initialize availServers by pushing all server indices into it, signifying that all servers are initially available.

• Iteratively process each request from the arrival vector:

  1. For each incoming request, first release any servers that have completed their tasks by the current request's start time from occupiedServers. Re-adjust and return these servers to availServers.
  2. Assign a free server from availServers to the incoming request. Update occupiedServers to include the server with its new finish time (current time + load).
  3. Increment the server's count in serverCount, indicating it has handled another request.

• After processing all requests:

  • Determine the maximum value in serverCount to identify the servers that handled the most requests.
  • Collect and return the indices of all servers that handled this maximum number of requests.

By using priority queues, the algorithm efficiently manages the servers and queues, scales well with the number of requests, and ensures all servers are utilized optimally based on their availability and load conditions.

class Solution {
    public List<Integer> getBusiestServers(int numServers, int[] arrivalTimes, int[] workLoads) {
        int[] requestCounts = new int[numServers];
        PriorityQueue<Integer> available = new PriorityQueue<>((x, y) -> x - y);
        PriorityQueue<Pair<Integer, Integer>> inUse = new PriorityQueue<>((x, y) -> x.getKey() - y.getKey());

        // Initialize all servers as available.
        for (int i = 0; i < numServers; ++i) {
            available.add(i);
        }
        
        for (int i = 0; i < arrivalTimes.length; ++i) {
            int currentTime = arrivalTimes[i];

            // Release and reassign servers based on availability and current time
            while (!inUse.isEmpty() && inUse.peek().getKey() <= currentTime) {
                Pair<Integer, Integer> current = inUse.poll();
                int serverIdx = current.getValue();
                int updatedIdx = ((serverIdx - i) % numServers + numServers) % numServers + i;
                available.add(updatedIdx);
            }

            // Assign server to handle current request
            if (!available.isEmpty()) {
                int nextServer = available.poll() % numServers;
                inUse.add(new Pair<>(currentTime + workLoads[i], nextServer));
                requestCounts[nextServer]++;
            }
        }
        
        // Determine servers with the highest number of requests handled
        int maxRequests = Collections.max(Arrays.stream(requestCounts).boxed().collect(Collectors.toList()));
        List<Integer> busiest = new ArrayList<>();
        for (int i = 0; i < numServers; ++i) {
            if (requestCounts[i] == maxRequests) {
                busiest.add(i);
            }
        }
        
        return busiest;
    }
}

In this Java solution, the goal is to identify the server(s) that handled the maximum number of requests among a given set of servers. The solution employs two primary data structures, each serving different purposes to efficiently manage server workload distribution and tracking:

• A PriorityQueue named available keeps track of servers that are immediately available to handle incoming requests. Servers are prioritized for assignment based on their numerical order, ensuring fair distribution of requests.

• Another PriorityQueue named inUse tracks servers that are currently busy handling requests. It pairs the time a server will be free with the server's index, allowing the system to manage server release and reassignment based on real-time availability.

The procedure performs the following steps:

1. Initializes all servers as available by adding each server's index to the available queue.

2. Iterates over each request's arrival time. For each time step:

   • Releases servers whose workload has been completed up to the current time. Reassigns their indices to reflect the circular nature of server assignment (using modular arithmetic).

   • Allocates the next available server to handle the incoming request. The server is then marked busy until it finishes handling its assigned workload, achieved by inserting its future availability time into the inUse queue.

   • Tracks the number of requests handled by each server using an array requestCounts, incrementing the count for the server handling the current request.

3. After all requests have been processed, the method checks requestCounts to identify the maximum number of requests handled by any server.

4. Compiles a list of all servers that achieved this maximum request count, thus identifying the busiest servers.

This method allows efficient distribution and tracking of workload across servers, utilizing priority queues to minimize idle time and ensure prompt response to incoming requests. The result is a list of server indices that represent the most loaded servers in terms of number of requests handled.