Rebalance shard ranges under overlap limit

Problem Statement

You are managing a distributed database where data is partitioned into shards. Each shard is defined as an interval [start, end] (inclusive). A configuration is considered "unstable" if more than k shards overlap at any single integer point on the number line.

You are given a list of n intervals and an integer k. Your goal is to modify the intervals such that the overlap constraint is satisfied. To minimize data migration, you must prioritize keeping existing boundaries fixed. For each shard that must be moved, you can shift its start or end boundary by the smallest possible integer amount to reduce the overlap.

Write a function rebalance_shards(intervals, k) that returns a new set of intervals satisfying the constraint. You should aim to resolve conflicts by shrinking intervals or shifting boundaries minimally.

Function Signature

def rebalance_shards(intervals, k):
    # intervals: List of tuples (start, end)
    # k: int
    # returns: List of tuples (start, end)

Examples

Example 1: Input: intervals = [(1, 5), (2, 6), (3, 7)], k = 2 Output: [(1, 2), (2, 6), (3, 7)] (One possible valid rebalancing) Explanation: At point 3, there are 3 overlaps. Shrinking the first interval to (1, 2) resolves the conflict.

Constraints

• n (number of intervals) = 1
• Interval coordinates are integers between 0 and 1,000,000.
• Time complexity should be better than O(n^2).