Least Connections Load Balancer
Description
A load balancer spreads requests across servers identical servers numbered from 0. Request i arrives at time arrivals[i] and holds one connection for durations[i] seconds, so its connection is active during [arrival, arrival + duration) and is already closed at time arrival + duration. Arrivals are non-decreasing. Each request is routed to the server with the fewest active connections at its arrival time, and ties go to the lowest-numbered server. Return the server index chosen for each request, in request order.
Examples
servers = 2, arrivals = [0,1,2,3,6], durations = [5,5,1,5,1][0,1,0,0,1]Server 0 takes the first request (busy until 5) and server 1 the second (busy until 6). At time 2 both hold one connection, so the tie goes to server 0, whose new connection ends at 3. At time 3 that short connection has just closed, so both servers again hold one connection and server 0 wins the tie. At time 6 server 0 still holds the connection that runs until 8 while server 1 has just become free, so server 1 is chosen.
servers = 3, arrivals = [0,0,0,1], durations = [10,10,10,1][0,1,2,0]Three requests arrive together and are spread over servers 0, 1 and 2 in turn, because each server in order has the fewest connections at that moment. The fourth request finds every server holding one connection, so the tie goes to server 0.
servers = 1, arrivals = [0,2,4], durations = [1,1,1][0,0,0]With a single server every request goes to server 0, whatever the load.
Constraints
- •
1 ≤ servers ≤ 100 - •
1 ≤ arrivals.length = durations.length ≤ 10⁴ - •
0 ≤ arrivals[i] ≤ 10⁹, non-decreasing - •
1 ≤ durations[i] ≤ 10⁶
Ready to solve this problem?
Practice solo and sharpen your skills for technical interviews.