Shard rebalancing with a per-key replica limit

Our key-value store spreads keys across shards. Each shard is given as a string "<id>:<start>:<end>" and owns every integer key in the inclusive range [start, end]. Shards may overlap. The depth of a key is the number of shards that cover it.

Implement:

def rebalance(limit: int, shards: list[str]) -> list[str]: ...

Return the rebalanced shards in the same "id:start:end" format, sorted by (start, id), so that:

1. No key has depth above limit (limit >= 1).
2. Earlier shards win. Process shards in order of (start, id). A shard placed earlier is never changed by a later one. A later shard resolves a conflict only by moving its start to the right, as little as possible. Its end stays. A shard left empty (start > end) is dropped.
3. No gaps. In the result, every key from the smallest original start to the largest original end is covered. Close a hole by extending the end of the kept shard that reaches furthest to its left, up to the key before the next shard.

You may not create new shard IDs or split a shard into two ranges. Keys fit in 64-bit integers and can be as large as 10^9. There are up to a few thousand shards.

Example 1

limit = 2
shards = ["x:0:50", "y:10:60", "z:20:70"]

Keys 20..50 are covered by three shards. x and y come first and stay. z moves its start to 51.

["x:0:50", "y:10:60", "z:51:70"]

Example 2

limit = 1
shards = ["a:0:10", "b:5:20", "c:30:40", "d:35:50"]

b moves to 11:20 and d moves to 41:50. Nothing covers keys 21..29, so b is extended to 29.

["a:0:10", "b:11:29", "c:30:40", "d:41:50"]