Given k servers numbered from 0 to k-1, you are given two integer arrays: arrival and load, both of length n. The i-th request arrives at time arrival[i] and takes load[i] units of time to process.
Each incoming request is assigned to a server as follows:
i is assigned to server i % k if that server is available at arrival[i].arrival[i], the request is dropped.arrival[i] + load[i].
Your task is to return a list of servers that handled the most number of requests.
Constraints: Each request must be handled by at most one server. Servers cannot process more than one request at a time. Elements must not be reused.
The brute-force approach is to check each server for every incoming request to see if it's available, but this quickly becomes inefficient as the number of servers and requests grows. Instead, we need an efficient way to keep track of which servers are available at any given time, and to assign requests according to the rules.
We realize that we need to:
i % k.To solve the problem efficiently, we use two main data structures:
arrival[i]):
i % k in the available set. If none is found, wrap around and check earlier indices.Why these data structures?
bisect) allows efficient lookup for the next available server in the required order.
Let's consider k = 3, arrival = [1,2,3,4,5], load = [5,2,3,3,3].
Final counts: server 0: 1, server 1: 2, server 2: 1. Server 1 handled the most requests.
Brute-force: For each request, checking all servers is O(nk), which is too slow for large inputs.
Optimized approach:
k servers in the worst case, but using a sorted set and heap, each operation is O(log k).
n requests, total time is O(n \log k).
O(k + n) for the heap, set, and request counts.
The problem tests your ability to efficiently simulate a resource allocation process with constraints. By using a min-heap to track busy servers and a sorted set to quickly find available servers, we can assign requests in optimal time. The key insight is to use data structures that allow for fast updates and lookups, making the algorithm both efficient and elegant.
import heapq
import bisect
class Solution:
def busiestServers(self, k, arrival, load):
n = len(arrival)
# Available servers (sorted list)
available = list(range(k))
# Busy servers: (end_time, server_index)
busy = []
# Count handled requests
count = [0] * k
for i, (start, duration) in enumerate(zip(arrival, load)):
# Free up servers whose jobs are done
while busy and busy[0][0] <= start:
end_time, server = heapq.heappop(busy)
bisect.insort(available, server)
if not available:
continue
idx = bisect.bisect_left(available, i % k)
if idx == len(available):
idx = 0
server = available.pop(idx)
count[server] += 1
heapq.heappush(busy, (start + duration, server))
max_count = max(count)
return [i for i, c in enumerate(count) if c == max_count]
#include <vector>
#include <set>
#include <queue>
using namespace std;
class Solution {
public:
vector<int> busiestServers(int k, vector<int>& arrival, vector<int>& load) {
int n = arrival.size();
set<int> available;
for (int i = 0; i < k; ++i) available.insert(i);
// busy: pair<end_time, server_index>
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> busy;
vector<int> count(k, 0);
for (int i = 0; i < n; ++i) {
int time = arrival[i];
int duration = load[i];
// Free up servers
while (!busy.empty() && busy.top().first <= time) {
available.insert(busy.top().second);
busy.pop();
}
if (available.empty()) continue;
auto it = available.lower_bound(i % k);
if (it == available.end()) it = available.begin();
int server = *it;
available.erase(it);
count[server]++;
busy.emplace(time + duration, server);
}
int max_count = *max_element(count.begin(), count.end());
vector<int> res;
for (int i = 0; i < k; ++i)
if (count[i] == max_count)
res.push_back(i);
return res;
}
};
import java.util.*;
class Solution {
public List<Integer> busiestServers(int k, int[] arrival, int[] load) {
int n = arrival.length;
TreeSet<Integer> available = new TreeSet<>();
for (int i = 0; i < k; ++i) available.add(i);
PriorityQueue<int[]> busy = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
int[] count = new int[k];
for (int i = 0; i < n; ++i) {
int time = arrival[i], duration = load[i];
while (!busy.isEmpty() && busy.peek()[0] <= time) {
available.add(busy.poll()[1]);
}
Integer server = available.ceiling(i % k);
if (server == null) server = available.isEmpty() ? null : available.first();
if (server == null) continue;
available.remove(server);
count[server]++;
busy.offer(new int[]{time + duration, server});
}
int max = Arrays.stream(count).max().getAsInt();
List<Integer> res = new ArrayList<>();
for (int i = 0; i < k; ++i)
if (count[i] == max)
res.add(i);
return res;
}
}
class MinHeap {
constructor() { this.heap = []; }
push(val) { this.heap.push(val); this._up(); }
pop() { if (!this.heap.length) return null; const top = this.heap[0]; const last = this.heap.pop(); if (this.heap.length) { this.heap[0] = last; this._down(); } return top; }
peek() { return this.heap[0]; }
_up() { let i = this.heap.length - 1; while (i > 0) { let p = (i - 1) >> 1; if (this.heap[i][0] < this.heap[p][0]) [this.heap[i], this.heap[p]] = [this.heap[p], this.heap[i]], i = p; else break; } }
_down() { let i = 0, n = this.heap.length; while (2 * i + 1 < n) { let l = 2 * i + 1, r = 2 * i + 2, j = l; if (r < n && this.heap[r][0] < this.heap[l][0]) j = r; if (this.heap[j][0] < this.heap[i][0]) [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]], i = j; else break; } }
}
var busiestServers = function(k, arrival, load) {
let n = arrival.length;
let available = [];
for (let i = 0; i < k; ++i) available.push(i);
let busy = new MinHeap();
let count = new Array(k).fill(0);
for (let i = 0; i < n; ++i) {
let time = arrival[i], duration = load[i];
// Free up servers
while (busy.heap.length && busy.peek()[0] <= time) {
let [_, server] = busy.pop();
let idx = binaryInsert(available, server);
}
if (!available.length) continue;
let idx = binarySearch(available, i % k);
if (idx == available.length) idx = 0;
let server = available.splice(idx, 1)[0];
count[server]++;
busy.push([time + duration, server]);
}
let max = Math.max(...count);
let res = [];
for (let i = 0; i < k; ++i)
if (count[i] == max)
res.push(i);
return res;
// insert server into available in sorted order
function binaryInsert(arr, val) {
let l = 0, r = arr.length;
while (l < r) {
let m = (l + r) >> 1;
if (arr[m] < val) l = m + 1;
else r = m;
}
arr.splice(l, 0, val);
return l;
}
// find first available server >= val
function binarySearch(arr, val) {
let l = 0, r = arr.length;
while (l < r) {
let m = (l + r) >> 1;
if (arr[m] < val) l = m + 1;
else r = m;
}
return l;
}
};