Range sharding must preserve key order: adjacent key buckets assigned to one shard form a contiguous range. The goal is to place range boundaries so the busiest shard is as small as possible.
Design a RangeShardBalancer class:
RangeShardBalancer() creates a stateless planner.int minimumMaxLoad(int[] bucketLoads, int numShards) returns the smallest possible maximum shard load after splitting all buckets into exactly numShards non-empty contiguous ranges.
bucketLoads[i] is the load of the next ordered key bucket. A bucket cannot be split or reordered. The load of a shard is the sum of its buckets.
Example 1:
Input:
Output:
Explanation: [10,20,30] and [40] have loads 60 and 40. Every alternative has a maximum of at least 60.
Example 2:
Input:
Output:
Explanation: The ranges [7,2,5] and [10,8] have loads 14 and 18.
Constraints
1 <= bucketLoads.length <= 10^50 <= bucketLoads[i] <= 10^61 <= numShards <= bucketLoads.length- The total bucket load fits in a signed 32-bit integer.
- At most
100 calls are made to minimumMaxLoad.
Balance Contiguous Range Shardshard