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:
ith (0-indexed) request arrives.(i % k)th server is available, assign the request to that server.ith server is busy, try to assign the request to the (i+1)th server, then the (i+2)th server, 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] <= 109arrival is strictly increasing.In #1606 Find Servers That Handled Most Number of Requests, the goal is to simulate how incoming requests are assigned to servers while tracking which servers handle the most tasks. The challenge comes from efficiently finding the next available server when requests arrive at different times.
A common approach combines a min-heap and an ordered set. The min-heap keeps track of busy servers based on the time they become free. When a new request arrives, servers that have finished processing are moved back into the available pool. An ordered set (or balanced structure) helps quickly find the next valid server index based on the request number using a circular allocation rule.
This design ensures fast updates and queries for server availability while maintaining request counts. After processing all requests, the servers with the highest handled counts are returned. The approach is efficient because each request triggers only logarithmic-time operations on the heap and set.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy with Min-Heap and Ordered Set | O(n log k) | O(k) |
Greg Hogg
Use these hints if you're stuck. Try solving on your own first.
To speed up the next available server search, keep track of the available servers in a sorted structure such as an ordered set.
To determine if a server is available, keep track of the end times for each task in a heap and add the server to the available set once the soonest task ending time is less than or equal to the next task to add.
This approach involves using a priority queue to manage and track the times when servers become available. Specifically, we will use a heap data structure to efficiently find the first available server for a new request. Whenever a request ends, we reassign the server for future tasks. We also utilize a balanced data structure to cycle through the server indexes and track the server with the most handled requests efficiently.
Time complexity: O(n log k), where n is the number of requests, due to the heap operations. Space complexity: O(k + n) for the heaps and request count.
1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5typedef struct {
6 int
The C solution uses explicit heap management to track the available servers and busy servers using arrays. Because C does not have built-in dynamic structures like sets or maps, this implementation takes a basic approach with efficient manual memory management, ensuring each step aligns correctly with the server allocation logic described in the problem.
Note: Due to the nature of C, the implementation details of heap operations like extract and heapify are omitted for brevity but are crucial for correct allocation of servers.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The ordered set helps efficiently locate the next available server index that is greater than or equal to the preferred server. If none exists, it wraps around to the smallest available server, supporting the circular allocation rule efficiently.
Yes, problems involving server scheduling, heaps, and ordered sets are common in technical interviews at large tech companies. This problem tests understanding of greedy simulation, priority queues, and efficient data structure usage.
A combination of a priority queue (min-heap) and an ordered set or balanced tree works best. The heap tracks when servers finish processing requests, while the ordered set quickly finds the next valid server index following the circular assignment rule.
The optimal approach uses a greedy simulation with a min-heap to track busy servers and an ordered set to maintain currently available servers. This allows efficient reassignment when servers become free and ensures each request is processed in logarithmic time.