Find Servers That Handled Most Number of Requests: Heap with Sorted Set

You have k servers numbered 0 through k-1 and a stream of requests. Each request i arrives at time arrival[i] and takes load[i] time to process. Request i should be assigned to server i % k first. If that server is busy, check the next server in circular order. If all servers are busy, the request is dropped. Return a list of the busiest servers, the ones that handled the most requests.

This is LeetCode 1606: Find Servers That Handled Most Number of Requests, and it is a great example of combining two data structures (a min-heap and a sorted set) to solve a scheduling problem efficiently.

Example: k = 3, arrival = [1,2,3,4,5], load = [5,2,3,3,8]. The answer is the server(s) that handled the most requests.

Why this problem matters

Server load balancing is not just an interview question. It models a real scenario: requests arrive over time, each server can handle one job at a time, and you need efficient scheduling. The round-robin-with-fallback pattern shows up in distributed systems, operating system schedulers, and connection pooling.

From an algorithmic perspective, this problem forces you to combine a min-heap (for tracking when servers become free) with a sorted set (for quickly finding the next available server in circular order). Neither data structure alone solves the problem efficiently. Learning to combine them is a skill that transfers to many other scheduling and resource allocation problems.

The key insight

The naive approach would check all k servers for every request, giving O(n * k) time. That is too slow when both n and k can be up to 10^5.

The key insight is to split the servers into two groups:

1. Busy servers, stored in a min-heap keyed by their finish time. When a request arrives, you pop all servers whose finish time is at or before the current arrival time, moving them back to the available pool.
2. Available servers, stored in a sorted set. When you need to assign a request to server i % k or the next available one in circular order, the sorted set lets you find it in O(log k) time.

The circular search is the trickiest part. You want the smallest available server ID that is >= i % k. If no such server exists (because all available servers have IDs smaller than i % k), you wrap around and take the smallest available server overall.

The solution

from sortedcontainers import SortedList
import heapq

def busiest_servers(k, arrival, load):
    count = [0] * k
    available = SortedList(range(k))
    busy = []

    for i in range(len(arrival)):
        t = arrival[i]

        while busy and busy[0][0] <= t:
            _, freed = heapq.heappop(busy)
            available.add(freed)

        if not available:
            continue

        preferred = i % k
        idx = available.bisect_left(preferred)
        if idx == len(available):
            idx = 0

        server = available[idx]
        available.remove(server)
        heapq.heappush(busy, (t + load[i], server))
        count[server] += 1

    max_count = max(count)
    return [i for i in range(k) if count[i] == max_count]

Let's walk through each part:

• available = SortedList(range(k)) initializes all servers as available, stored in a sorted set for O(log k) lookups.
• Freeing servers: Before processing each request, pop all entries from the busy heap whose finish time is at or before the current arrival time. Add each freed server back to the sorted set.
• Finding the next server: Use bisect_left(preferred) to find the first available server at or after the preferred index i % k. If idx reaches the end of the sorted list, wrap around to index 0.
• Assigning: Remove the chosen server from the available set, push it onto the busy heap with its finish time, and increment its count.

Visual walkthrough

Let's trace through a complete example with k = 3, arrival = [1,2,3,4,8], load = [5,2,3,3,2].

Complexity analysis

The O(n log k) time is a massive improvement over the O(n * k) brute force. When k = 100,000 and n = 100,000, the brute force does 10 billion operations. The heap + sorted set approach does roughly 1.7 million.

The building blocks

This problem is built from two core building blocks that appear in many other problems:

Min-heap for event scheduling

Use a min-heap to track "when does the next event happen?" Pop events as time progresses. This is the same pattern used in Task Scheduler (tracking cooldowns), meeting room problems (tracking end times), and merge-k-sorted-lists (tracking the smallest current element). The template:

import heapq

heap = []
for event in events:
    while heap and heap[0][0] <= current_time:
        _, item = heapq.heappop(heap)
        process_freed(item)
    heapq.heappush(heap, (end_time, item))

Sorted set for circular search

Use a sorted container to find the next available item in O(log n) time. The bisect_left operation finds the insertion point, and wrapping around handles the circular case. This pattern appears in problems where you need "the next element at or above a threshold" with dynamic insertions and deletions.

from sortedcontainers import SortedList

available = SortedList()
idx = available.bisect_left(target)
if idx == len(available):
    idx = 0
chosen = available[idx]
available.remove(chosen)

Edge cases

• All servers always busy. If every request arrives while all k servers are occupied, every request gets dropped. All counts stay 0, and you return all server IDs.
• Single server (k = 1). Every request targets server 0. The server handles one request at a time, dropping any that arrive while it is busy.
• Requests with zero load. A request with load[i] = 0 is processed instantly. The server becomes free immediately at time arrival[i] + 0 = arrival[i], so it can handle the next request arriving at the same time.
• All requests fit without conflict. If arrivals are spaced far enough apart that no server is ever busy, every request goes to its preferred server. The round-robin gives a uniform distribution.

From understanding to recall

The tricky part of this problem is not the idea. "Use a heap for busy servers and a sorted set for available servers" is easy to remember conceptually. The part that slips under pressure is the circular search logic: computing i % k, using bisect_left, and handling the wrap-around when the index reaches the end of the sorted list.

Spaced repetition locks this in. You write the solution from scratch, and after a few reps at increasing intervals, the bisect_left / wrap-around pattern becomes automatic. CodeBricks breaks the problem into its two building blocks so you can practice the heap scheduling and the sorted set search independently before combining them.

Related posts

• Task Scheduler - Uses greedy frequency counting for CPU scheduling, another scheduling problem with a different twist
• Kth Largest Element in an Array - Demonstrates the min-heap building block used here for tracking the k largest elements

---

Visual Learner? See how heaps work under the hood with our Data Structures: Trees Guide.