LeetCode 1606 - Find Servers That Handled Most Number of Requests

LeetCode Problem 1606

Difficulty: 🔴 Hard
Topics: Array, Heap (Priority Queue), Simulation, Ordered Set

Solution

Problem Understanding

The problem presents a simulation scenario involving k servers, each uniquely identified from 0 to k-1. Every server can handle only one request at a time, and requests arrive at discrete times given by the strictly increasing arrival array. Each request requires a certain load of time to complete. Requests are assigned to servers based on a modular rule: the ith request prefers server (i % k); if that server is busy, the assignment wraps around to the next available server, starting from that server and looping back to 0 if necessary. If all servers are busy, the request is dropped.

The input consists of an integer k representing the number of servers, an array arrival of strictly increasing positive integers representing arrival times of requests, and an array load representing the processing time for each request.

The output is a list of server IDs that handled the maximum number of requests. Multiple servers may share the maximum count, and the order of IDs does not matter.

Key constraints include a large upper limit (k and arrival.length up to 10^5) and strictly increasing arrival times. This eliminates naive O(k * n) approaches because such solutions would be too slow. Edge cases to consider include all servers busy at certain times, ties in request counts, and single-server scenarios.

Approaches

Brute Force Approach

The naive approach would iterate over each request, checking servers sequentially starting from (i % k) and moving forward to find an available server. If no server is free, the request is dropped. This requires scanning up to k servers per request, resulting in a time complexity of O(n * k). While correct, this is too slow for large k and n (up to 10^5 each), making it impractical for the given constraints.

Optimal Approach

The key insight is to efficiently track which servers are available and which are busy at a given time. Using two data structures achieves this:

1. A min-heap (priority queue) to store busy servers and their release times, allowing us to quickly free servers when a request arrives.
2. An ordered set of available server IDs to efficiently find the next free server starting from (i % k) and wrapping around.

The algorithm works as follows: for each arriving request, we first release all servers whose completion time is less than or equal to the current arrival. Then we locate the first available server >= (i % k), wrapping around if necessary. If a server is found, we assign the request, update its busy time, and increase its count. After processing all requests, we return servers with the maximum handled requests.

Algorithm Walkthrough

1. Initialize an array request_count of size k to 0 to track how many requests each server handled.

2. Create a min-heap busy_servers to store tuples (release_time, server_id) representing servers that are currently processing requests.

3. Initialize a sorted set available_servers containing all server IDs [0, 1, ..., k-1].

4. Iterate over each request i with arrival[i] and load[i]:

5. Free servers: pop all servers from busy_servers whose release_time <= arrival[i] and add their IDs back to available_servers.

6. Search for the first available server ID >= (i % k). If none exists, wrap around and select the smallest available server ID.

7. If no server is available, drop the request.

8. Otherwise, assign the request to the chosen server:

9. Remove the server from available_servers.

10. Push (arrival[i] + load[i], server_id) into busy_servers.

11. Increment request_count[server_id].

12. After processing all requests, find the maximum value in request_count.

13. Return all server IDs whose count equals the maximum.

Why it works: By maintaining a heap of busy servers and a sorted set of available servers, we can assign requests in O(log k) time per request while ensuring the modular preference and wrap-around requirement. The request counts are accurate because each request is handled exactly once or dropped.

Python Solution

from typing import List
import heapq
from sortedcontainers import SortedSet

class Solution:
    def busiestServers(self, k: int, arrival: List[int], load: List[int]) -> List[int]:
        request_count = [0] * k
        busy_servers = []
        available_servers = SortedSet(range(k))

        for i, (start, duration) in enumerate(zip(arrival, load)):
            while busy_servers and busy_servers[0][0] <= start:
                _, freed_server = heapq.heappop(busy_servers)
                available_servers.add(freed_server)

            if not available_servers:
                continue

            index = available_servers.bisect_left(i % k)
            if index == len(available_servers):
                index = 0
            server_id = available_servers[index]

            available_servers.remove(server_id)
            heapq.heappush(busy_servers, (start + duration, server_id))
            request_count[server_id] += 1

        max_requests = max(request_count)
        return [i for i, count in enumerate(request_count) if count == max_requests]

The code first initializes request tracking and server availability. For each incoming request, it frees up completed servers using a min-heap. Using a SortedSet, it efficiently finds the next available server according to the modular rule, wraps if necessary, assigns the request, and updates the counters. Finally, it returns the servers with maximum handled requests.

Go Solution

package main

import (
    "container/heap"
    "sort"
)

type Server struct {
    endTime int
    id      int
}

type MinHeap []Server

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].endTime < h[j].endTime }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x interface{}) {
    *h = append(*h, x.(Server))
}

func (h *MinHeap) Pop() interface{} {
    n := len(*h)
    item := (*h)[n-1]
    *h = (*h)[:n-1]
    return item
}

func busiestServers(k int, arrival []int, load []int) []int {
    requestCount := make([]int, k)
    available := make([]int, k)
    for i := 0; i < k; i++ {
        available[i] = i
    }

    busy := &MinHeap{}
    heap.Init(busy)

    for i, start := range arrival {
        duration := load[i]
        for busy.Len() > 0 && (*busy)[0].endTime <= start {
            freed := heap.Pop(busy).(Server).id
            index := sort.SearchInts(available, freed)
            available = append(available[:index], append([]int{freed}, available[index:]...)...)
        }

        if len(available) == 0 {
            continue
        }

        idx := sort.Search(len(available), func(j int) bool { return available[j] >= i%k })
        if idx == len(available) {
            idx = 0
        }
        serverID := available[idx]
        available = append(available[:idx], available[idx+1:]...)
        heap.Push(busy, Server{endTime: start + duration, id: serverID})
        requestCount[serverID]++
    }

    maxReq := 0
    for _, cnt := range requestCount {
        if cnt > maxReq {
            maxReq = cnt
        }
    }

    res := []int{}
    for i, cnt := range requestCount {
        if cnt == maxReq {
            res = append(res, i)
        }
    }
    return res
}

The Go solution mirrors the Python approach. Instead of a SortedSet, it uses a slice and binary search for insertion and lookup. The min-heap keeps track of busy servers. Server assignment, request counting, and final maximum detection follow the same logic.

Worked Examples

Example 1: k=3, arrival=[1,2,3,4,5], load=[5,2,3,3,3]