LeetCode #1606 — HARD

Find Servers That Handled Most Number of Requests

Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.

The Problem

Problem Statement

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 i^th (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). For example, if the i^th 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 i^th request, and another array load, where load[i] represents the load of the i^th 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 <= 10⁵
1 <= arrival.length, load.length <= 10⁵
arrival.length == load.length
1 <= arrival[i], load[i] <= 10⁹
arrival is strictly increasing.

Step 01

Brute Force Baseline

Problem summary: 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). For example, if the 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

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Array · Segment Tree

Example 1

3
[1,2,3,4,5]
[5,2,3,3,3]

Example 2

3
[1,2,3,4]
[1,2,1,2]

Example 3

3
[1,2,3]
[10,12,11]

Core Insight

What unlocks the optimal approach

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.

Interview move: turn each hint into an invariant you can check after every iteration/recursion step.

Step 03

Algorithm Walkthrough

Iteration Checklist

Define state (indices, window, stack, map, DP cell, or recursion frame).
Apply one transition step and update the invariant.
Record answer candidate when condition is met.
Continue until all input is consumed.

Use the first example testcase as your mental trace to verify each transition.

Step 04

Edge Cases

Minimum Input

Single element / shortest valid input

Validate boundary behavior before entering the main loop or recursion.

Duplicates & Repeats

Repeated values / repeated states

Decide whether duplicates should be merged, skipped, or counted explicitly.

Extreme Constraints

Largest constraint values

Re-check complexity target against constraints to avoid time-limit issues.

Invalid / Corner Shape

Empty collections, zeros, or disconnected structures

Handle special-case structure before the core algorithm path.

Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #1606: Find Servers That Handled Most Number of Requests
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;
    }
}

// Accepted solution for LeetCode #1606: Find Servers That Handled Most Number of Requests
func busiestServers(k int, arrival, load []int) (ans []int) {
	free := redblacktree.NewWithIntComparator()
	for i := 0; i < k; i++ {
		free.Put(i, nil)
	}
	busy := hp{}
	cnt := make([]int, k)
	for i, t := range arrival {
		for len(busy) > 0 && busy[0].end <= t {
			free.Put(busy[0].server, nil)
			heap.Pop(&busy)
		}
		if free.Size() == 0 {
			continue
		}
		p, _ := free.Ceiling(i % k)
		if p == nil {
			p = free.Left()
		}
		server := p.Key.(int)
		cnt[server]++
		heap.Push(&busy, pair{t + load[i], server})
		free.Remove(server)
	}
	mx := slices.Max(cnt)
	for i, v := range cnt {
		if v == mx {
			ans = append(ans, i)
		}
	}
	return
}

type pair struct{ end, server int }
type hp []pair

func (h hp) Len() int           { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].end < h[j].end }
func (h hp) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any)        { *h = append(*h, v.(pair)) }
func (h *hp) Pop() any          { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }

# Accepted solution for LeetCode #1606: Find Servers That Handled Most Number of Requests
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]

// Accepted solution for LeetCode #1606: Find Servers That Handled Most Number of Requests
/**
 * [1606] Find Servers That Handled Most Number of Requests
 *
 * 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 i^th (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). For example, if the i^th 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 i^th request, and another array load, where load[i] represents the load of the i^th 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:
 * <img alt="" src="https://assets.leetcode.com/uploads/2020/09/08/load-1.png" style="width: 389px; height: 221px;" />
 * 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 <= 10^5
 * 	1 <= arrival.length, load.length <= 10^5
 * 	arrival.length == load.length
 * 	1 <= arrival[i], load[i] <= 10^9
 * 	arrival is strictly increasing.
 *
 */
pub struct Solution {}

// problem: https://leetcode.com/problems/find-servers-that-handled-most-number-of-requests/
// discuss: https://leetcode.com/problems/find-servers-that-handled-most-number-of-requests/discuss/?currentPage=1&orderBy=most_votes&query=

// submission codes start here

impl Solution {
    // Credit: https://leetcode.com/problems/find-servers-that-handled-most-number-of-requests/solutions/942408/rust-binary-heap-and-btreeset/
    pub fn busiest_servers(k: i32, arrival: Vec<i32>, load: Vec<i32>) -> Vec<i32> {
        let k = k as usize;
        let mut servers = std::collections::BTreeSet::new();
        for i in 0..k {
            servers.insert(i);
        }

        let mut active_requests: std::collections::BinaryHeap<std::cmp::Reverse<(i32, usize)>> =
            std::collections::BinaryHeap::new();
        let mut iterator = arrival.iter().zip(load.iter()).peekable();
        let mut requests = vec![0; k];
        let mut i = 0;

        while let Some(&(&t2, &l)) = iterator.peek() {
            if active_requests.peek().is_none() || (active_requests.peek().unwrap().0).0 > t2 {
                let (time, load) = iterator.next().unwrap();

                if servers.len() > 0 {
                    let s = if let Some(server) = servers.range(i..).next() {
                        *server
                    } else {
                        *servers.range(..).next().unwrap()
                    };
                    servers.remove(&s);
                    requests[s] += 1;
                    active_requests.push(std::cmp::Reverse((time + load, s)));
                }
                i += 1;
                i %= k;
            } else {
                let std::cmp::Reverse((_, server)) = active_requests.pop().unwrap();
                servers.insert(server);
            }
        }

        let max_r = *requests.iter().max().unwrap();
        requests
            .iter()
            .enumerate()
            .filter(|x| *x.1 == max_r)
            .map(|x| x.0 as i32)
            .collect()
    }
}

// submission codes end

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_1606_example_1() {
        let k = 3;
        let arrival = vec![1, 2, 3, 4, 5];
        let load = vec![5, 2, 3, 3, 3];

        let result = vec![1];

        assert_eq!(Solution::busiest_servers(k, arrival, load), result);
    }

    #[test]
    fn test_1606_example_2() {
        let k = 3;
        let arrival = vec![1, 2, 3, 4];
        let load = vec![1, 2, 1, 2];

        let result = vec![0];

        assert_eq!(Solution::busiest_servers(k, arrival, load), result);
    }

    #[test]
    fn test_1606_example_3() {
        let k = 3;
        let arrival = vec![1, 2, 3];
        let load = vec![10, 12, 11];

        let result = vec![0, 1, 2];

        assert_eq!(Solution::busiest_servers(k, arrival, load), result);
    }
}

// Accepted solution for LeetCode #1606: Find Servers That Handled Most Number of Requests
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #1606: Find Servers That Handled Most Number of Requests
// 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;
//     }
// }

Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Custom checkpoints (one per line)

Press Step or Run All to begin.

Step 07

Complexity Analysis

Time

O(n + q log n)

Space

O(n)

Approach Breakdown

BRUTE FORCE

O(n × q) time

O(1) space

For each of q queries, scan the entire range to compute the aggregate (sum, min, max). Each range scan takes up to O(n) for a full-array query. With q queries: O(n × q) total. Point updates are O(1) but queries dominate.

SEGMENT TREE

O(n + q log n) time

O(n) space

Building the tree is O(n). Each query or update traverses O(log n) nodes (tree height). For q queries: O(n + q log n) total. Space is O(4n) ≈ O(n) for the tree array. Lazy propagation adds O(1) per node for deferred updates.

Shortcut: Build O(n), query/update O(log n) each. When you need both range queries AND point updates.

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Off-by-one on range boundaries

Wrong move: Loop endpoints miss first/last candidate.

Usually fails on: Fails on minimal arrays and exact-boundary answers.

Fix: Re-derive loops from inclusive/exclusive ranges before coding.