Find Servers That Handled Most Number of Requests

Find Servers That Handled Most Number of Requests - Problem

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.

Input & Output

Example 1 — Basic Assignment

$ Input: k = 3, arrival = [1,2,3,4,5], load = [5,2,3,3,3]

› Output: [1]

💡 Note: Server 0 gets requests 0,3 (2 requests), Server 1 gets requests 1,4 (2 requests), Server 2 gets request 2 (1 request). All tie with 2 requests each, but Server 1 handled most efficiently.

Example 2 — Request Dropping

$ Input: k = 3, arrival = [1,2,3,4], load = [1,2,1,2]

› Output: [0]

💡 Note: Server 0 handles request 0 (finishes at time 2), Server 1 handles request 1 (finishes at time 4), Server 2 handles request 2 (finishes at time 4). Request 3 arrives at time 4 when all servers are busy, so it's dropped.

Example 3 — Wrapping Around

$ Input: k = 2, arrival = [1,2,3], load = [2,1,1]

› Output: [0,1]

💡 Note: Server 0 gets request 0, Server 1 gets request 1. Request 2 prefers server 0 but it's busy, so wraps to server 1. Both servers handle 1 request each.

Constraints

1 ≤ k ≤ 10⁵
1 ≤ arrival.length, load.length ≤ 10⁵
arrival.length == load.length
1 ≤ arrival[i], load[i] ≤ 10⁹
arrival is strictly increasing.

Visualization

Tap to expand

Understanding the Visualization

Input

k=3 servers, requests arrive at [1,2,3,4,5] with loads [5,2,3,3,3]

Process

Assign requests using rotation and availability rules

Output

Return servers with maximum request count

Key Takeaway

🎯 Key Insight: Use priority queues to efficiently manage server availability and avoid O(k) linear searches per request

Asked in

A Amazon 15 G Google 12 M Microsoft 8 F Facebook 6

The key insight is to efficiently track server availability and completion times. The optimal approach uses priority queues and ordered sets to avoid linear searches. Time: O(n log k), Space: O(k)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(n×k)	O(k)	Simulate each request by checking all servers linearly
Optimized with Priority Queues	O(n log k)	O(k)	Use heaps to efficiently track server availability and assignment order

Brute Force Simulation — Algorithm Steps

For each request, calculate preferred server (i % k)
If preferred server is free, assign request
Otherwise, linearly search all servers starting from preferred
Update server completion time and increment request count

Visualization

Tap to expand

Step-by-Step Walkthrough

Request Assignment

Calculate preferred server (i % k)

Linear Search

Check servers sequentially if preferred is busy

Update State

Assign request and update server completion time

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void solution(int k, int* arrival, int arrivalSize, int* load, int* result, int* resultSize) {
    int* serverFreeTime = (int*)calloc(k, sizeof(int));
    int* requestCount = (int*)calloc(k, sizeof(int));
    
    for (int i = 0; i < arrivalSize; i++) {
        int preferred = i % k;
        int currentTime = arrival[i];
        
        // Check if preferred server is available
        if (serverFreeTime[preferred] <= currentTime) {
            serverFreeTime[preferred] = currentTime + load[i];
            requestCount[preferred]++;
        } else {
            // Find next available server
            int assigned = 0;
            for (int j = 0; j < k; j++) {
                int serverId = (preferred + j) % k;
                if (serverFreeTime[serverId] <= currentTime) {
                    serverFreeTime[serverId] = currentTime + load[i];
                    requestCount[serverId]++;
                    assigned = 1;
                    break;
                }
            }
        }
    }
    
    // Find servers with maximum requests
    int maxRequests = 0;
    for (int i = 0; i < k; i++) {
        if (requestCount[i] > maxRequests) {
            maxRequests = requestCount[i];
        }
    }
    
    *resultSize = 0;
    for (int i = 0; i < k; i++) {
        if (requestCount[i] == maxRequests) {
            result[(*resultSize)++] = i;
        }
    }
    
    free(serverFreeTime);
    free(requestCount);
}

int main() {
    int k;
    scanf("%d", &k);
    
    char line[10000];
    scanf(" %s", line);
    
    // Parse arrival array
    int arrival[1000];
    int arrivalSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token) {
        arrival[arrivalSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    scanf(" %s", line);
    
    // Parse load array
    int load[1000];
    int loadSize = 0;
    token = strtok(line + 1, ",]");
    while (token) {
        load[loadSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result[1000];
    int resultSize;
    solution(k, arrival, arrivalSize, load, result, &resultSize);
    
    printf("[");
    for (int i = 0; i < resultSize; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n×k)

For each of n requests, we may need to check all k servers to find available one

✓ Linear Growth

Space Complexity

O(k)

Arrays to track server completion times and request counts

✓ Linear Space

23.4K Views

Medium Frequency

~35 min Avg. Time

567 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler