Find Servers That Handled Most Number of Requests
HardPrompt
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)thserver 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). For example, if the
ithserver is busy, try to assign the request to the(i+1)thserver, then the(i+2)thserver, and so on.
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.
Example 1:
Input: k = 3, arrival = [1,2,3,4,5], load = [5,2,3,3,3]
Output: [1]
Explanation:
All of the servers start out available.
The first 3 requests are handled by the first 3 servers in order.
Request 3 comes in. Server 0 is busy, so it's assigned to the next available server, which is 1.
Request 4 comes in. It cannot be handled since all servers are busy, so it is dropped.
Servers 0 and 2 handled one request each, while server 1 handled two requests. Hence server 1 is the busiest server.Example 2:
Input: k = 3, arrival = [1,2,3,4], load = [1,2,1,2]
Output: [0]
Explanation:
The first 3 requests are handled by first 3 servers.
Request 3 comes in. It is handled by server 0 since the server is available.
Server 0 handled two requests, while servers 1 and 2 handled one request each. Hence server 0 is the busiest server.Example 3:
Input: k = 3, arrival = [1,2,3], load = [10,12,11]
Output: [0,1,2]
Explanation: Each server handles a single request, so they are all considered the busiest.
Constraints:
1 <= k <= 1051 <= arrival.length, load.length <= 105arrival.length == load.length1 <= arrival[i], load[i] <= 109arrivalis strictly increasing.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly simulates the server assignment process as described in the problem. For each incoming request, it performs a linear scan through the servers to find an available one, following the specified wrap-around logic. While simple to conceptualize, its performance degrades significantly as the number of servers increases.
Algorithm
-
- Initialize
requestCountsandfinishTimesarrays of sizekwith zeros.
- Initialize
-
- For each request
ifrom0ton-1:
- a. Iterate through potential servers
jfrom0tok-1. - b. Calculate the server index to check:
serverIdx = (i + j) % k. - c. If
finishTimes[serverIdx] <= arrival[i], the server is available. - d. Assign the request: update
finishTimes[serverIdx], incrementrequestCounts[serverIdx], and break the inner loop to proceed to the next request.
- For each request
-
- After the main loop, find the maximum value in
requestCounts.
- After the main loop, find the maximum value in
-
- Return a list of all server indices whose count matches the maximum.
Walkthrough
We maintain two arrays of size k: requestCounts to track the number of requests handled by each server, and finishTimes to store the time each server becomes free. We iterate through each request. For the i-th request arriving at arrival[i], we check servers starting from i % k, then (i+1) % k, and so on, wrapping around. The first server j we find whose finishTimes[j] is less than or equal to arrival[i] is assigned the request. We then update finishTimes[j] to arrival[i] + load[i] and increment requestCounts[j]. If the entire loop over k servers completes without finding an available one, the request is dropped. After processing all requests, we find the maximum value in requestCounts and return the indices of all servers that achieved this count.
import java.util.ArrayList;import java.util.List; class Solution { public List<Integer> busiestServers(int k, int[] arrival, int[] load) { int[] requestCounts = new int[k]; long[] finishTimes = new long[k]; for (int i = 0; i < arrival.length; i++) { long currentTime = arrival[i]; int preferredServer = i % k; int serverToUse = -1; for (int j = 0; j < k; j++) { int serverIndex = (preferredServer + j) % k; if (finishTimes[serverIndex] <= currentTime) { serverToUse = serverIndex; break; } } if (serverToUse != -1) { finishTimes[serverToUse] = currentTime + load[i]; requestCounts[serverToUse]++; } } int maxRequests = 0; for (int count : requestCounts) { maxRequests = Math.max(maxRequests, count); } List<Integer> busiest = new ArrayList<>(); for (int i = 0; i < k; i++) { if (requestCounts[i] == maxRequests) { busiest.add(i); } } return busiest; }}Complexity
Time
O(N * K), where `N` is the number of requests and `K` is the number of servers. For each of the `N` requests, we might scan up to `K` servers.
Space
O(K) to store `requestCounts` and `finishTimes`.
Trade-offs
Pros
Easy to understand and implement.
Low memory overhead compared to more complex solutions.
Cons
Time complexity is too high for the given constraints, likely resulting in a 'Time Limit Exceeded' error.
This approach significantly improves the efficiency of the simulation by using appropriate data structures. A min-priority queue is used to manage busy servers, and a TreeSet (a balanced binary search tree) is used to manage available servers. This combination allows for fast updates of server availability and efficient searching for the next server to assign a request to.
Algorithm
-
- Initialize
requestCountsarray of sizekwith zeros.
- Initialize
-
- Create a
TreeSetavailableServersand populate it with server IDs from0tok-1.
- Create a
-
- Create a min-priority queue
busyServersto store[finishTime, serverId]pairs.
- Create a min-priority queue
-
- For each request
ifrom0ton-1:
- a. Let
currentTime = arrival[i]. - b. Free up finished servers: move servers from
busyServerstoavailableServersif their finish time is<= currentTime. - c. If
availableServersis empty, drop the request and continue. - d. Determine the target server: find
server_id = availableServers.ceiling(i % k). If it's null, useavailableServers.first(). - e. Assign the request: remove
server_idfromavailableServers, increment its count, and add[currentTime + load[i], server_id]tobusyServers.
- For each request
-
- After the loop, find the maximum value in
requestCounts.
- After the loop, find the maximum value in
-
- Return a list of all server indices whose count matches the maximum.
Walkthrough
We maintain a count of requests for each server in an array. To manage server states, we use two main data structures: a min-priority queue busyServers that stores [finishTime, serverId] pairs, ordered by finishTime, and a TreeSet availableServers that stores the IDs of available servers. Initially, all servers are in availableServers. For each request i arriving at currentTime, we first update our set of available servers by polling from busyServers all servers whose finishTime is less than or equal to currentTime and adding them back to availableServers. If availableServers is empty, the request is dropped. Otherwise, we find the appropriate server using the TreeSet. We search for the smallest server ID greater than or equal to i % k using availableServers.ceiling(i % k). If such a server doesn't exist (i.e., ceiling returns null), we wrap around and take the smallest available server ID, given by availableServers.first(). The chosen server is then removed from availableServers, its request count is incremented, and it's added to busyServers with its new finish time. Finally, we identify and return the busiest servers based on the counts.
import java.util.*; class Solution { public List<Integer> busiestServers(int k, int[] arrival, int[] load) { int[] requestCounts = new int[k]; PriorityQueue<long[]> busyServers = new PriorityQueue<>(Comparator.comparingLong(a -> a[0])); TreeSet<Integer> availableServers = new TreeSet<>(); for (int i = 0; i < k; i++) { availableServers.add(i); } for (int i = 0; i < arrival.length; i++) { long currentTime = arrival[i]; while (!busyServers.isEmpty() && busyServers.peek()[0] <= currentTime) { long[] finishedServer = busyServers.poll(); availableServers.add((int) finishedServer[1]); } if (availableServers.isEmpty()) { continue; } int targetServer = i % k; Integer serverId = availableServers.ceiling(targetServer); if (serverId == null) { serverId = availableServers.first(); } availableServers.remove(serverId); requestCounts[serverId]++; long finishTime = currentTime + load[i]; busyServers.add(new long[]{finishTime, (long)serverId}); } int maxRequests = 0; for (int count : requestCounts) { maxRequests = Math.max(maxRequests, count); } List<Integer> busiest = new ArrayList<>(); for (int i = 0; i < k; i++) { if (requestCounts[i] == maxRequests) { busiest.add(i); } } return busiest; }}Complexity
Time
O(N * log K). Each of the `N` requests involves a few operations (add, remove, poll, ceiling) on the `TreeSet` and `PriorityQueue`, which have a size of at most `K`. Each operation takes `O(log K)` time.
Space
O(K). The `TreeSet` and `PriorityQueue` can store up to `K` elements.
Trade-offs
Pros
Highly efficient and passes the given constraints.
Scales well with a large number of servers and requests.
Cons
More complex to implement due to the use of advanced data structures.
Slightly higher constant factor in time and space complexity compared to the naive approach, though asymptotically superior.
Solutions
Solution
class Solution { public List < Integer > busiestServers ( int k , int [] arrival , int [] load ) { int [] cnt = new int [ k ]; PriorityQueue < int []> busy = new PriorityQueue <>( Comparator . comparingInt ( a -> a [ 0 ])); TreeSet < Integer > free = new TreeSet <>(); for ( int i = 0 ; i < k ; ++ i ) { free . add ( i ); } for ( int i = 0 ; i < arrival . length ; ++ i ) { int start = arrival [ i ]; int end = start + load [ i ]; while (! busy . isEmpty () && busy . peek ()[ 0 ] <= start ) { free . add ( busy . poll ()[ 1 ]); } if ( free . isEmpty ()) { continue ; } Integer server = free . ceiling ( i % k ); if ( server == null ) { server = free . first (); } ++ cnt [ server ]; busy . offer ( new int [] { end , server }); free . remove ( server ); } int mx = 0 ; for ( int v : cnt ) { mx = Math . max ( mx , v ); } List < Integer > ans = new ArrayList <>(); for ( int i = 0 ; i < k ; ++ i ) { if ( cnt [ i ] == mx ) { ans . add ( i ); } } return ans ; } }class Solution { public: vector < int > busiestServers ( int k , vector < int >& arrival , vector < int >& load ) { set < int > free ; for ( int i = 0 ; i < k ; ++ i ) free . insert ( i ); priority_queue < pair < int , int > , vector < pair < int , int >> , greater <>> busy ; vector < int > cnt ( k ); for ( int i = 0 ; i < arrival . size (); ++ i ) { int start = arrival [ i ], end = start + load [ i ]; while ( ! busy . empty () && busy . top (). first <= start ) { free . insert ( busy . top (). second ); busy . pop (); } if ( free . empty ()) continue ; auto p = free . lower_bound ( i % k ); if ( p == free . end ()) p = free . begin (); int server = * p ; ++ cnt [ server ]; busy . emplace ( end , server ); free . erase ( server ); } int mx = * max_element ( cnt . begin (), cnt . end ()); vector < int > ans ; for ( int i = 0 ; i < k ; ++ i ) if ( cnt [ i ] == mx ) ans . push_back ( i ); return ans ; } };from sortedcontainers import SortedList class Solution : def busiestServers ( self , k : int , arrival : List [ int ], load : List [ int ]) -> List [ int ]: free = SortedList ( range ( k )) busy = [] cnt = [ 0 ] * k for i , ( start , t ) in enumerate ( zip ( arrival , load )): while busy and busy [ 0 ][ 0 ] <= start : free . add ( busy [ 0 ][ 1 ]) heappop ( busy ) if not free : continue j = free . bisect_left ( i % k ) if j == len ( free ): j = 0 server = free [ j ] cnt [ server ] += 1 heappush ( busy , ( start + t , server )) free . remove ( server ) mx = max ( cnt ) return [ i for i , v in enumerate ( cnt ) if v == mx ]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.