Weighted round robin sends more requests to servers with greater configured capacity. A naive implementation can create bursts by sending a server all of its weighted turns together. Smooth weighted round robin preserves the same long-run proportions while spreading each server's selections across the sequence.
Design a SmoothWeightedRoundRobin class:
SmoothWeightedRoundRobin(int[] weights) initializes one server per array index. All current weights start at 0.int pick() selects and returns a server index.
For each call to pick():
- Add
weights[i] to every server's current weight. - Select the server with the largest current weight. If several servers tie, select the smallest index.
- Subtract the sum of all static weights from the selected server's current weight.
- Keep the resulting current weights for the next call.
Do not mutate the input array.
Example 1:
Input:
Output:
Explanation: The total weight is 7. Server 0 is selected five times, and servers 1 and 2 are each selected once. Their turns are distributed through the sequence rather than grouped into three bursts.
Example 2:
Input:
Output:
Explanation: One cycle contains five selections. Server 0 receives three, server 1 receives two, and the selections alternate as evenly as their weights allow.
Constraints
1 <= weights.length <= 1001 <= weights[i] <= 10^4- At most
10^5 calls are made to pick. - If current weights tie, return the smallest server index.
- The constructor must copy any input state it needs instead of retaining a mutable alias to
weights.
Design a Smooth Weighted Round Robin Schedulermedium