Rebalance shard ranges under overlap limit

You maintain a set of data shards. Each shard owns an inclusive integer key range [start, end].

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).