1606. Find Servers That Handled Most Number of Requests

/**
 * Problem: LeetCode 1606 - Find Servers That Handled Most Number of Requests
 * Difficulty: Hard
 * Language: Java
 * Author: CodeByTushu
 */
import java.util.*;

class Solution {
    public List<Integer> busiestServers(int k, int[] arrival, int[] load) {
        int[] count = new int[k];

        // Self-balancing BST to track currently available server IDs
        TreeSet<Integer> free = new TreeSet<>();
        for (int i = 0; i < k; i++) free.add(i);

        // Min-heap tracking busy servers: {completionTime, serverId}
        PriorityQueue<long[]> busy = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));

        for (int i = 0; i < arrival.length; i++) {
            long start = arrival[i];

            // Free all servers that have finished before or at current arrival time
            while (!busy.isEmpty() && busy.peek()[0] <= start) {
                free.add((int) busy.poll()[1]);
            }

            // If all servers are occupied, request is dropped
            if (free.isEmpty()) continue;

            // Cyclic lookup: find smallest available server >= (i % k), wrapping to first()
            Integer server = free.ceiling(i % k);
            if (server == null) server = free.first();

            free.remove(server);
            count[server]++;
            busy.offer(new long[]{start + load[i], server});
        }

        // Find the maximum number of requests handled
        int max = 0;
        for (int c : count) max = Math.max(max, c);

        // Collect all server IDs achieving the maximum request count
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            if (count[i] == max) result.add(i);
        }
        return result;
    }
}

"""
Problem: LeetCode 1606 - Find Servers That Handled Most Number of Requests
Difficulty: Hard
Language: Python 3
Author: CodeByTushu
"""
import heapq


class Solution:
    def busiestServers(self, k: int, arrival: list[int], load: list[int]) -> list[int]:
        count = [0] * k
        free_ge = list(range(k))  # Available servers with ID >= (i % k)
        free_lt = []              # Available servers with ID < (i % k)
        busy = []                 # Min-heap of (completion_timestamp, server_id)

        for i, (start, duration) in enumerate(zip(arrival, load)):
            target = i % k

            # When request index modulo resets to 0, flush wrapped servers back
            if target == 0:
                while free_lt:
                    heapq.heappush(free_ge, heapq.heappop(free_lt))

            # Release all servers whose task finishes on or before the current start time
            while busy and busy[0][0] <= start:
                _, s = heapq.heappop(busy)
                if s >= target:
                    heapq.heappush(free_ge, s)
                else:
                    heapq.heappush(free_lt, s)

            # Rebalance servers whose ID is strictly less than target
            while free_ge and free_ge[0] < target:
                heapq.heappush(free_lt, heapq.heappop(free_ge))

            # Pick the lowest available server >= target, or wrap around
            if free_ge:
                server = heapq.heappop(free_ge)
            elif free_lt:
                server = heapq.heappop(free_lt)
            else:
                continue  # All k servers busy -> request is dropped

            count[server] += 1
            heapq.heappush(busy, (start + duration, server))

        max_req = max(count)
        return [idx for idx, c in enumerate(count) if c == max_req]

/**
 * Problem: LeetCode 1606 - Find Servers That Handled Most Number of Requests
 * Difficulty: Hard
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>
#include <set>
#include <queue>
#include <algorithm>

class Solution {
public:
    std::vector<int> busiestServers(int k, std::vector<int>& arrival, std::vector<int>& load) {
        std::vector<int> count(k, 0);

        // Balanced BST of available server indices (supports lower_bound in O(log k))
        std::set<int> free;
        for (int i = 0; i < k; ++i) {
            free.insert(i);
        }

        // Min-heap tracking busy servers: {completionTime, serverId}
        std::priority_queue<std::pair<long long, int>, 
                            std::vector<std::pair<long long, int>>, 
                            std::greater<std::pair<long long, int>>> busy;

        for (int i = 0; i < arrival.size(); ++i) {
            long long start = arrival[i];

            // Free all servers that have finished before or at current arrival time
            while (!busy.empty() && busy.top().first <= start) {
                free.insert(busy.top().second);
                busy.pop();
            }

            if (free.empty()) continue; // All servers busy -> request dropped

            // Find smallest server index >= (i % k), wrapping to begin() if needed
            auto it = free.lower_bound(i % k);
            if (it == free.end()) {
                it = free.begin();
            }

            int server = *it;
            free.erase(it);
            count[server]++;
            busy.push({start + load[i], server});
        }

        int max_val = *std::max_element(count.begin(), count.end());
        std::vector<int> result;
        for (int i = 0; i < k; ++i) {
            if (count[i] == max_val) {
                result.push_back(i);
            }
        }
        return result;
    }
};

/**
 * Problem: LeetCode 1606 - Find Servers That Handled Most Number of Requests
 * Difficulty: Hard
 * Language: JavaScript
 * Author: CodeByTushu
 */

/**
 * MinHeap implementation for PriorityQueue operations
 */
class MinHeap {
    constructor(comparator = (a, b) => a - b) {
        this.heap = [];
        this.comp = comparator;
    }
    size() { return this.heap.length; }
    peek() { return this.heap[0]; }
    push(val) {
        this.heap.push(val);
        this._siftUp(this.heap.length - 1);
    }
    pop() {
        if (this.size() === 0) return null;
        const top = this.heap[0];
        const last = this.heap.pop();
        if (this.size() > 0) {
            this.heap[0] = last;
            this._siftDown(0);
        }
        return top;
    }
    _siftUp(i) {
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.comp(this.heap[i], this.heap[p]) < 0) {
                [this.heap[i], this.heap[p]] = [this.heap[p], this.heap[i]];
                i = p;
            } else break;
        }
    }
    _siftDown(i) {
        const n = this.heap.length;
        while ((i << 1) + 1 < n) {
            let left = (i << 1) + 1;
            let right = left + 1;
            let best = i;
            if (this.comp(this.heap[left], this.heap[best]) < 0) best = left;
            if (right < n && this.comp(this.heap[right], this.heap[best]) < 0) best = right;
            if (best !== i) {
                [this.heap[i], this.heap[best]] = [this.heap[best], this.heap[i]];
                i = best;
            } else break;
        }
    }
}

/**
 * @param {number} k
 * @param {number[]} arrival
 * @param {number[]} load
 * @return {number[]}
 */
var busiestServers = function(k, arrival, load) {
    const count = new Array(k).fill(0);
    const freeGe = new MinHeap(); // Available servers with ID >= (i % k)
    for (let i = 0; i < k; i++) freeGe.push(i);
    const freeLt = new MinHeap(); // Available servers with ID < (i % k)
    const busy = new MinHeap((a, b) => a[0] - b[0]); // [completionTime, serverId]

    for (let i = 0; i < arrival.length; i++) {
        const start = arrival[i];
        const duration = load[i];
        const target = i % k;

        // Wrap around when target resets to 0
        if (target === 0) {
            while (freeLt.size() > 0) freeGe.push(freeLt.pop());
        }

        // Release servers that finish at or before current request's arrival
        while (busy.size() > 0 && busy.peek()[0] <= start) {
            const [, s] = busy.pop();
            if (s >= target) freeGe.push(s);
            else freeLt.push(s);
        }

        // Move servers with ID < target to the wrapped pool
        while (freeGe.size() > 0 && freeGe.peek() < target) {
            freeLt.push(freeGe.pop());
        }

        // Assign request to the next available server >= target or wrap around
        let server = null;
        if (freeGe.size() > 0) {
            server = freeGe.pop();
        } else if (freeLt.size() > 0) {
            server = freeLt.pop();
        } else {
            continue; // All k servers busy -> request is dropped
        }

        count[server]++;
        busy.push([start + duration, server]);
    }

    let maxReq = 0;
    for (let c of count) {
        if (c > maxReq) maxReq = c;
    }

    const result = [];
    for (let i = 0; i < k; i++) {
        if (count[i] === maxReq) result.push(i);
    }
    return result;
};