Question
## Scenario A service partitions an integer keyspace into named shards. Configuration changes may introduce overlapping ranges or gaps. Normalize the configuration so that no key belongs to more than `limit` shards while preserving coverage of the original outer envelope whenever at least one shard remains. Each shard is encoded as `"id:start:end"`, where `start` and `end` are inclusive integers and `start <= end`. ## Interface ```python def rebalance(limit: int, shards: list[str]) -> list[str]: ... ``` ## Rules - Process shards in ascending order of `(start, end, id)`. - A previously accepted shard has priority over a later overlapping shard. - Trim the start of a later shard until accepting it would not exceed `limit` coverage at that key. - If the entire later shard is covered at the limit, drop it. - After overlap trimming, close an interior gap by extending the most recently retained shard up to the next retained shard’s start minus one. - Preserve the minimum start and maximum end of the original input by extending the first or last retained shard if necessary. - Return normalized strings ordered by `(start, end, id)`. - For an empty input, return an empty list. Assume `limit >= 1` and shard identifiers contain no colon. ## Example ```text limit = 1 shards = ["a:0:4", "b:3:7", "c:10:12"] result = ["a:0:4", "b:5:9", "c:10:12"] ``` Shard `b` yields keys `3–4` to `a`; then it stretches through the gap before `c`. ## Edge cases - Multiple ranges with the same start. - A range fully contained in an earlier range. - Negative keys and single-key ranges. - A chain where trimming one range changes which shard should close the next gap. ## Follow-ups 1. Add or remove a shard while moving as few keys as possible. 2. Return an explicit migration plan rather than only the final ranges. 3. Support very large sparse ranges without iterating through every key. 4. Generalize from one replica to a configurable replication factor and failure domains.