1606. Find Servers That Handled Most Number of Requests

HardGreedyArrayOrdered SetHeap (Priority Queue)
Leetcode Link

Problem Description

In this LeetCode problem, we are given k servers, each capable of handling only one request at a time. Multiple requests, represented by their arrival times and loads (duration to complete), arrive and need to be assigned to these servers. The mechanism for assigning requests to servers follows a specific algorithm:

  • The i-th request arrives.
  • If all servers are currently busy, the request is dropped.
  • If the server at index (i % k) is available, the request is assigned there.
  • If that server is busy, we proceed to the next server in a round-robin fashion until we find an available server or conclude that all are busy.

The goal is to find which server(s) gets the most requests. The returned list should contain the ID(s) of the busiest server(s).

Intuition

For the solution, we need efficient ways to track available and busy servers, along with the count of handled requests. Here is the intuition broken down:

  • Use a data structure to keep track of free servers that allows for efficient retrieval and insertion based on server indices. A SortedList can be appropriate here as it maintains the elements in a sorted order.

  • Have a way to keep track of the busy servers along with the time they will become free. A min-heap, where the key is the time when the server gets free, can serve this purpose because it can quickly tell us the next server that will become free.

  • Maintain a list to count the number of requests each server has handled. This will help in identifying the busiest server(s).

  • Iterate over each request, updating the free and busy lists accordingly:

    • Make any server that has finished its load free.
    • If there is a free server, assign the request to the server that follows the given criteria.
    • Update the count of requests handled by the chosen server.
    • If no free server is found, drop the request.

  • Finding the index of the free server that comes after (i % k) can be done using binary search in the SortedList. If the index is out of range, we start from the beginning of the list (ensuring the round-robin behavior).

  • After evaluating all requests, identify the maximum number of requests handled by any server. Then, compile a list of all servers that achieved this maximum.

The provided solution implements these steps, efficiently managing requests and server availability to conclude which servers were the busiest.

Learn more about Greedy and Heap (Priority Queue) patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which type of traversal does breadth first search do?

Solution Approach

The implementation of the solution uses Python's SortedList from the sortedcontainers module and a min-heap to manage the efficient tracking of free and busy servers. The steps followed in the implementation are as follows:

  1. Initialize a SortedList named free with all server indices from 0 to k-1 to represent all servers being free initially.

  2. Create an empty list busy which will function as a min-heap to track busy servers and when they will be free. Each element in busy is a tuple consisting of the time the server will be free and the server index.

  3. cnt is an array of zeros with length k which will be used to count the number of requests each server has successfully handled.

  4. Loop through each request by enumerating over paired arrival and load values.

  5. Inside the loop, first deal with servers that have completed their requests:

    • While there is a server in the busy list whose end time is less than or equal to the current request's start time, remove and add it to free servers. This operation is done using heappop which removes the smallest element from the busy list.

  6. If there are no free servers, the current request is dropped, as per the algorithm. Continue to the next iteration.

  7. Otherwise, find the correct server:

    • Use free.bisect_left(i % k) to find the position in free to insert i % k and maintain sorted order. If j is out of range (meaning no free servers with index greater than or equal to i % k), wrap around to the start of the list (j=0).

  8. Once the server is identified, increment the corresponding server's handled request count in cnt.

  9. Push the end time of the current request, along with the server index, to the busy list using heappush, so it's now considered busy until that time. Remove the server from free.

  10. After processing all requests, determine the maximum number of handled requests by any server.

  11. Iterate over cnt and collect the indices corresponding to this maximum number of requests.

The implementation closely follows the initial intuition and uses Python's built-in data structures to efficiently manage the problem's constraints. By doing so, the solution avoids brute-force approaches and can handle large sets of data within the required time constraints.

Combining these data structures with linear processing of requests (aided by logarithmic operations for adding/removing servers from sorted structures) allows the algorithm to remain scalable and performant.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following array represent a max heap?

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Assume we have k=3 servers and a list of requests where each request is represented as a tuple of (arrival time, load):

Requests: [(1,4), (2,3), (3,4), (4,2)]

Steps:

  1. Initialize free = SortedList([0, 1, 2]), as all servers are free initially.
  2. busy = [] is initially empty since no servers are busy at the start.
  3. cnt = [0, 0, 0] is used to count the number of requests handled by each server.

Now, let's iterate over each request:

Request (1,4):

  • Server 0 (as 1%3=1) is free, assign this request to Server 0.
  • Update cnt to [1, 0, 0].
  • Add Server 0 with the time it will be free (1+4=5) to busy.
  • Update free to [1, 2].

Request (2,3):

  • Server 1 (as 2%3=2) is free, assign this request to Server 1.
  • Update cnt to [1, 1, 0].
  • Add Server 1 with the time it will be free (2+3=5) to busy.
  • Update free to [2].

Request (3,4):

  • Server 2 (as 3%3=0) is free, assign this request to Server 2.
  • Update cnt to [1, 1, 1].
  • Add Server 2 with the time it will be free (3+4=7) to busy.
  • Update free to [].

Request (4,2):

  • Check busy servers to see if any have become free. None have, because the current arrival time 4 is not greater than 5 or 7.
  • All servers are busy (free is empty), so this request is dropped.

After all requests:

  • busy eventually clears as time progresses, adding servers back to free.
  • Final cnt is [1, 1, 1].

Conclusion:

  • The maximum number of handled requests by any server is 1.
  • All servers handled exactly 1 request, so they are all the busiest.

According to our approach, the output would be [0, 1, 2], as these are the indices of servers with the maximum count of handled requests. The implemented solution effectively tracked servers' statuses and requests, resulting in an efficient and scalable algorithm.

Solution Implementation

1from sortedcontainers import SortedList
2from heapq import heappush, heappop
3
4class Solution:
5    def busiestServers(self, server_count: int, arrival_times: list, process_time: list) -> list:
6        # Initialize a sorted list with server indices
7        available_servers = SortedList(range(server_count))
8      
9        # List to keep track of servers that are currently busy
10        busy_servers = []
11      
12        # Counter for the number of times each server has been used
13        request_count = [0] * server_count
14      
15        # Iterate over all arrival times and corresponding processing times
16        for i, (arrival_time, duration) in enumerate(zip(arrival_times, process_time)):
17          
18            # Free up servers that have finished processing according to current arrival time
19            while busy_servers and busy_servers[0][0] <= arrival_time:
20                finished_server = busy_servers[0][1]
21                available_servers.add(finished_server)
22                heappop(busy_servers)
23          
24            # If there are no free servers, skip to next request
25            if not available_servers:
26                continue
27          
28            # Find an available server starting from the server with index i modulo server_count
29            server_index = available_servers.bisect_left(i % server_count)
30          
31            # If the index is beyond the last server, wrap around to the first server
32            if server_index == len(available_servers):
33                server_index = 0
34          
35            # Assign selected server for current request
36            assigned_server = available_servers[server_index]
37          
38            # Increase the count of the requests handled by the server
39            request_count[assigned_server] += 1
40          
41            # Mark the server as busy by scheduling its next free time
42            heappush(busy_servers, (arrival_time + duration, assigned_server))
43          
44            # Remove the server from available servers since it is now busy
45            available_servers.remove(assigned_server)
46
47        # Find the maximum number of requests handled by a server
48        max_requests = max(request_count)
49      
50        # Determine all servers that have handled the maximum number of requests
51        busiest_servers = [server for server, count in enumerate(request_count) if count == max_requests]
52      
53        return busiest_servers
54
1class Solution {
2    public List<Integer> busiestServers(int k, int[] arrival, int[] load) {
3        // Count array to keep track of requests handled by each server
4        int[] count = new int[k];
5        // Priority queue to manage currently busy servers (end time, server index)
6        PriorityQueue<int[]> busyServers = new PriorityQueue<>((a, b) -> a[0] - b[0]);
7        // TreeSet to manage available servers
8        TreeSet<Integer> availableServers = new TreeSet<>();
9        for (int i = 0; i < k; ++i) {
10            availableServers.add(i);
11        }
12        for (int i = 0; i < arrival.length; ++i) {
13            int startTime = arrival[i];
14            int endTime = startTime + load[i];
15            // Release servers that have completed their tasks
16            while (!busyServers.isEmpty() && busyServers.peek()[0] <= startTime) {
17                availableServers.add(busyServers.poll()[1]);
18            }
19            // Continue to next request if no servers are available
20            if (availableServers.isEmpty()) {
21                continue;
22            }
23            // Find the server with the closest index after i % k
24            Integer serverIndex = availableServers.ceiling(i % k);
25            // If no such server is found, get the first available server
26            if (serverIndex == null) {
27                serverIndex = availableServers.first();
28            }
29            // Increment the request count for this server
30            ++count[serverIndex];
31            // Add server to busy servers with corresponding end time
32            busyServers.offer(new int[] {endTime, serverIndex});
33            // Remove this server from the set of available servers
34            availableServers.remove(serverIndex);
35        }
36        // Find the max value in the count array
37        int maxCount = 0;
38        for (int value : count) {
39            maxCount = Math.max(maxCount, value);
40        }
41        // Collect all servers that have this max request count
42        List<Integer> busiestServers = new ArrayList<>();
43        for (int i = 0; i < k; ++i) {
44            if (count[i] == maxCount) {
45                busiestServers.add(i);
46            }
47        }
48        return busiestServers;
49    }
50}
51
1#include <vector>
2#include <set>
3#include <queue>
4#include <algorithm>
5
6class Solution {
7public:
8    vector<int> busiestServers(int k, vector<int>& arrival, vector<int>& load) {
9        // Initialize a set to keep track of available servers
10        set<int> availableServers;
11        for (int i = 0; i < k; ++i) {
12            availableServers.insert(i);
13        }
14
15        // Priority queue to manage busy servers based on their end time
16        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> busyServers;
17      
18        // Vector to hold the count of requests handled by each server
19        vector<int> requestCount(k, 0);
20
21        // Iterate over each request
22        for (int i = 0; i < arrival.size(); ++i) {
23            int startTime = arrival[i];
24            int endTime = startTime + load[i];
25
26            // Free up servers that have completed their tasks
27            while (!busyServers.empty() && busyServers.top().first <= startTime) {
28                availableServers.insert(busyServers.top().second);
29                busyServers.pop();
30            }
31
32            // If there are no available servers, skip to the next request
33            if (availableServers.empty()) {
34                continue;
35            }
36
37            // Find the first server that can take the current request
38            auto serverIterator = availableServers.lower_bound(i % k);
39            if (serverIterator == availableServers.end()) {
40                serverIterator = availableServers.begin();
41            }
42
43            // Assign the task to the server
44            int assignedServer = *serverIterator;
45            ++requestCount[assignedServer];
46            busyServers.emplace(endTime, assignedServer);
47
48            // Remove the server from the available set as it's now busy
49            availableServers.erase(assignedServer);
50        }
51
52        // Find the maximum number of requests handled by any server
53        int maxRequests = *max_element(requestCount.begin(), requestCount.end());
54
55        // Collect all servers that handled the max number of requests
56        vector<int> busiestServers;
57        for (int i = 0; i < k; ++i) {
58            if (requestCount[i] == maxRequests) {
59                busiestServers.push_back(i);
60            }
61        }
62
63        return busiestServers;
64    }
65};
66
1// Importing the standard libraries for data structures and algorithms
2import { PriorityQueue } from 'typescript-collections';
3
4// Define a Pair class to hold pairs of values
5class Pair<T, U> {
6    constructor(public first: T, public second: U) {}
7}
8
9// Define a Comparator interface for priority queue
10interface Comparator<T> {
11    compare(o1: T, o2: T): number;
12}
13
14// Define a function to find the busiest servers
15function busiestServers(k: number, arrival: number[], load: number[]): number[] {
16    // Initialize a set to keep track of available servers
17    const availableServers = new Set<number>();
18    for (let i = 0; i < k; ++i) {
19        availableServers.add(i);
20    }
21
22    // Function to compare pairs for priority queue
23    const pairComparator: Comparator<Pair<number, number>> = {
24        compare: (o1, o2) => {
25            if (o1.first !== o2.first) {
26                return o1.first - o2.first;
27            }
28            return o1.second - o2.second;
29        },
30    };
31
32    // Initialize a priority queue to manage busy servers based on their end time
33    const busyServers = new PriorityQueue(pairComparator);
34
35    // Array to hold the count of requests handled by each server
36    const requestCount: number[] = new Array(k).fill(0);
37
38    // Iterate over each request
39    arrival.forEach((startTime, i) => {
40        const endTime = startTime + load[i];
41
42        // Free up servers that have completed their tasks
43        while (!busyServers.isEmpty() && busyServers.peek().first <= startTime) {
44            availableServers.add(busyServers.dequeue().second);
45        }
46
47        // If there are no available servers, skip to the next request
48        if (availableServers.size === 0) {
49            return;
50        }
51
52        // Find the first server that can take the current request
53        let assignedServer = -1;
54        for (let j = 0; j < k; j++) {
55            const serverId = (i + j) % k;
56            if (availableServers.has(serverId)) {
57                assignedServer = serverId;
58                break;
59            }
60        }
61
62        // Assign the task to the server if one is found
63        if (assignedServer !== -1) {
64            requestCount[assignedServer]++;
65            busyServers.enqueue(new Pair(endTime, assignedServer));
66
67            // Remove the server from the available set as it's now busy
68            availableServers.delete(assignedServer);
69        }
70    });
71
72    // Find the maximum number of requests handled by any server
73    const maxRequests = Math.max(...requestCount);
74
75    // Collect all servers that handled the max number of requests
76    const busiestServers: number[] = [];
77    requestCount.forEach((count, index) => {
78        if (count === maxRequests) {
79            busiestServers.push(index);
80        }
81    });
82
83    return busiestServers;
84}
85
86// Please note that you might need to implement or import a PriorityQueue
87// and ensure the TypeScript environment is setup with all necessary typings.
88
Not Sure What to Study? Take the 2-min Quiz：

What's the relationship between a tree and a graph?

Time and Space Complexity

Time Complexity

The time complexity of the code consists of several parts:

  1. Initialization: Initializing the free sorted list with range(k) takes O(k * log(k)) because it's creating a sorted list of k servers.
  2. Processing requests: The for loop runs n times where n is the number of requests (the length of arrival).
  3. Freeing up servers: The inner while loop pops elements from the heap busy which has at most k elements. Each heappop operation takes O(log(k)) time. In the worst case, all servers are freed in one iteration so the complexity can be O(k * log(k)) but averaged over n iterations it doesn't exceed n * log(k) adding to the total complexity.
  4. Finding the server: Using bisect_left on the SortedList has a time complexity of O(log(k)) for searching. This operation is executed once per request.
  5. Updating the heap and list: heappush into busy takes O(log(k)) and removing an element from free takes O(log(k)) as well.

Considering these parts together: Initialization is O(k * log(k)). The for loop runs n times, within it:

  • The freeing of servers is O(n * log(k)) over n iterations.
  • Finding the server is O(log(k)) for each request, so O(n * log(k)) in total.
  • Updating the heap and list is O(2 * log(k)) for each request, resulting in O(n * log(k)).

So the total time complexity is O(k * log(k) + n * log(k) + n * log(k) + n * log(k)), which simplifies to O((k + 3n) * log(k)).

Space Complexity

The space complexity is determined by the space required for:

  1. SortedList free: which holds at most k elements, so it is O(k).
  2. Heap busy: in the worst case, it can hold k elements simultaneously, so it is O(k).
  3. List cnt: it is a list of length k, hence O(k).
  4. Output list: in the worst case where all servers have the maximum count, the output list can also have k elements, so it is O(k).

The space complexity is therefore the sum of all these parts, which is O(k) + O(k) + O(k) + O(k), which simplifies to O(k).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following array represent a max heap?

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

Heap Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫