You are implementing a shard management system for a distributed key-value store.
Each shard is represented as a string in the format "id:start:end", where the shard covers the inclusive key range [start, end].
Given an integer limit and an array shards, rebalance the shards so that:
No key is covered by more than limit shards.
Processing happens after sorting the original shards by start ascending, then end ascending.
If a shard would cover a key that already has limit active shards, shift that shard's start to the earliest key where coverage becomes strictly less than limit.
If shifting makes start > end, delete that shard.
After all shifts and deletions, coverage must stay continuous from the original minimum start to the original maximum end. If a gap appears, extend the most recently kept shard to fill it.
Return the rebalanced shards in the same "id:start:end" format. You may return them in any order.
Identifiers are distinct and do not contain colons.
Examples
Example 1:
Input: limit = 2, shards = ["A:0:100", "B:40:110", "C:80:200", "D:210:300"]
Output: ["A:0:100", "B:40:110", "C:101:209", "D:210:300"]
Explanation:
Shard C cannot start at 80 because keys 80..100 are already covered by A and B. It shifts to 101. Then C is extended to 209 to fill the gap before D.
Example 2:
Input: limit = 1, shards = ["A:0:100", "B:80:180"]
Output: ["A:0:100", "B:101:180"]
Example 3:
Input: limit = 2, shards = ["A:0:30", "B:0:31", "C:0:32", "D:0:100"]
Output: ["A:0:30", "B:0:31", "C:31:32", "D:32:100"]
Explanation:
After A and B, shard C must move to 31. Shard D is processed later and must start after the saturated region, so it becomes 32:100.
Constraints
1 <= limit <= 10^5
0 <= shards.length <= 10^4
-10^9 <= start <= end <= 10^9
Each shard string has the format "id:start:end".
Shard identifiers are distinct and contain no colons.
Sort shards by (start, end), then sweep from left to right. Maintain a min-heap of active shard ends plus a last_start guard so later shards cannot move back into a prefix that was already proven saturated. After the sweep, extend the previous kept shard whenever there is a gap so coverage stays continuous from the original minimum start to the original maximum end.
Sorting enforces the required priority order, so earlier shards always win. Whenever limit active shards already cover the candidate start, jumping to earliestEnd + 1 is the smallest shift that can reduce overlap. If that jump moves past the shard's end, the shard is fully eclipsed and must be dropped. Gap filling only extends the immediate predecessor, so it restores continuity without creating new overlap.
Time: O(n log n)
Space: O(n)
import heapq
class Solution:
def rebalance(self, limit: int, shards: List[str]) -> List[str]:
if not shards:
return []
parsed = []
max_end = -10**18
for shard in shards:
shard_id, start_raw, end_raw = shard.split(':')
start = int(start_raw)
end = int(end_raw)
parsed.append([shard_id, start, end])
if end > max_end:
max_end = end
parsed.sort(key=lambda shard: (shard[1], shard[2]))
end_heap = []
last_start = -10**18
kept = []
for shard_id, start, end in parsed:
new_start = max(start, last_start)
tentative = []
while True:
while end_heap and end_heap[0] < new_start:
heapq.heappop(end_heap)
if len(end_heap) < limit:
break
smallest = heapq.heappop(end_heap)
tentative.append(smallest)
new_start = smallest + 1
if new_start > end:
for value in tentative:
heapq.heappush(end_heap, value)
continue
kept.append([shard_id, new_start, end])
heapq.heappush(end_heap, end)
last_start = new_start
if kept:
cover_end = kept[0][2]
for i in range(1, len(kept)):
prev = kept[i - 1]
cur = kept[i]
if cur[1] > cover_end + 1:
prev[2] = cur[1] - 1
cover_end = prev[2]
if cur[2] > cover_end:
cover_end = cur[2]
if kept[-1][2] < max_end:
kept[-1][2] = max_end
return [f"{shard_id}:{start}:{end}" for shard_id, start, end in kept]