321. Load Balancing Requests to Available Servers

Load Balancing Requests to Available Servers

Implement a load-balancing algorithm for n servers numbered from 1 to n that process m incoming requests.

Each request has an arrival time and an execution duration. When a request arrives, assign it to the available server with the lowest server number. If every server is busy, drop the request.

Method Signature

List<Integer> assignRequests(int n, List<Integer> arrival, List<Integer> burstTime)

m = arrival.size() = burstTime.size() is the number of requests.
n is the number of servers.
arrival.get(i) is the arrival time of request i.
burstTime.get(i) is the execution duration of request i.
Return a list where the value at index i is the server number assigned to request i.
Return -1 at index i when request i is dropped.

Assignment Rules

Servers are numbered from 1 to n.
All servers are initially available.
Requests are processed in their input order.
If multiple requests have the same arrival time, the request appearing at the lower index is processed first.
A request is assigned to the available server with the lowest server number.
A server assigned request i remains busy until time arrival.get(i) + burstTime.get(i).
A server becomes available for another request arriving exactly at its completion time.
If no server is available when a request arrives, that request is dropped and represented by -1.
Dropped requests do not affect the availability of any server.

Constraints

1 ≤ n ≤ 100,000
1 ≤ arrival.size() ≤ 100,000
arrival.size() = burstTime.size()
0 ≤ arrival.get(i) ≤ 1,000,000,000
1 ≤ burstTime.get(i) ≤ 1,000,000,000
arrival.get(i) ≤ arrival.get(i + 1) for every valid index i.

Examples

Example 1

assignRequests(n = 3, arrival = [1, 2, 2, 5, 6], burstTime = [5, 2, 3, 1, 2])

Output: [1, 2, 3, 2, 1]

The first three requests occupy servers 1, 2, and 3. At time 5, servers 2 and 3 are available, so server 2 is selected. At time 6, server 1 is available and has the lowest server number.

Example 2

assignRequests(n = 2, arrival = [0, 1, 2, 3, 5], burstTime = [5, 4, 1, 1, 2])

Output: [1, 2, -1, -1, 1]

Both servers are busy at times 2 and 3, so those requests are dropped. Both servers become available at time 5, and server 1 is selected.

Example 3

assignRequests(n = 2, arrival = [4, 4, 4, 7], burstTime = [3, 1, 2, 1])

Output: [1, 2, -1, 1]

Requests with the same arrival time are processed in input order. The first two requests occupy both servers, so the third request is dropped. Server 1 becomes available exactly at time 7 and receives the final request.