You maintain a set of data shards. Each shard owns an **inclusive** integer key range `[start, end]`. ```python class Shard: id: str start: int end: int class Shards: def __init__(self, limit: int): # provided ... def add_shard(self, shard: Shard): # provided ... def remove_shard(self, shard_id: str): # provided ... def rebalance(self): # TODO ... ``` ### Goal Implement `rebalance()` so that after it runs, the shard ranges satisfy all of the following: 1. **Overlap constraint:** For every key `k`, the number of shards whose ranges contain `k` is **≤ `limit`**. 2. **No gaps within the global span:** Let `L = min(original starts)` and `R = max(original ends)` over the shards currently stored. After rebalancing, every key in `[L, R]` must be covered by **at least 1** shard. 3. **Minimize data movement heuristic (tie-breaking rule):** When you must adjust ranges to eliminate overlaps, prefer modifying the shard(s) that start **later** (i.e., with larger `start`) before modifying earlier shards. (Intuition: moving later ranges tends to move less data.) 4. **Valid ranges:** Every remaining shard must have `start <= end`. If a shard becomes empty (e.g., `start > end`) after adjustments, it should be removed. You may reorder internal storage as needed, and you may modify shard `start/end`, remove shards, and/or create/extend ranges as needed to satisfy the constraints. ### Example `limit = 1` Input shards: - `('A', 0, 100)` - `('B', 80, 180)` One valid rebalance result (using the “modify later shard first” rule): - `('A', 0, 100)` - `('B', 101, 180)` Because keys `80..100` overlapped with `limit=1`, shard `B` (which starts later) is shifted to start at `101`. ### Notes / Constraints - Shards may be provided in any order. - Assume up to `N` shards (e.g., `N` can be large), and key values can be large integers. - Define clearly in your implementation whether `rebalance()` returns the final list (for testing) or just mutates internal state (either is acceptable as long as it is consistent).