带边界约束的Interval重叠消除算法优化求助（含C#实现问题）

需求说明 #

给定一组区间列表，以及一个边界范围Boundary，需要设计算法最小位移调整列表中的区间，满足两个条件：

1. 所有区间彼此无重叠
2. 所有区间完全处于Boundary范围内

示例 #

• 示例1：
  输入：[[4,7],[5,7]]，边界：[0,10]
  输出：[[4,7],[7,9]]
• 示例2：
  输入：[[6,8],[6,9]]，边界：[0,10]
  输出：[[5,7],[7,10]]
• 示例3：
  输入：[[0,1],[5,6],[6,8],[6,9]]，边界：[0,10]
  输出：[[0,1],[4,5],[5,7],[7,10]]

现有尝试问题 #

初始递归版本问题 #

初始C#实现采用递归处理重叠，但当3个及以上区间靠近边界时会陷入无限递归：

public class Bookshelf
{
    public List<Tuple<int, int>> Intervals { get; private set; }
    public Tuple<int, int> Boundary { get; private set; }

    public Bookshelf(List<Tuple<int, int>> intervals, Tuple<int, int> boundary)
    {
        Intervals=intervals;
        Boundary=boundary;
        Intervals.Sort((a, b) =>
        {
            int compareStart = a.Item1.CompareTo(b.Item1);
            return compareStart != 0 ? compareStart : a.Item2.CompareTo(b.Item2);
        });
        foreach (var overlap in FindOverlaps())
            HandleOverlap(overlap);
    }
    public static int Range(Tuple<int, int> interval) => interval.Item2 - interval.Item1;
    public bool IsEnoughSpace(Tuple<int, int> interval) => (Intervals.Sum(item => Range(item)) + Range(interval)) <= Range(Boundary);
    public int IsInBound(Tuple<int, int> interval) => (Boundary.Item1 <= interval.Item1) && (Boundary.Item2 >= interval.Item2) ? 0 : (Boundary.Item1 > interval.Item1) ? -1 : 1;
    public void AddInterval(Tuple<int, int> interval)
    {
        if (!IsEnoughSpace(interval)) throw new Exception("Not enough space");
        if (IsInBound(interval) != 0) throw new Exception("Not in Bound");
        Intervals.Add(interval);
        Intervals.Sort((a, b) =>
        {
            int compareStart = a.Item1.CompareTo(b.Item1);
            return compareStart != 0 ? compareStart : a.Item2.CompareTo(b.Item2);
        });
        foreach(var overlap in FindOverlaps())
            HandleOverlap(overlap);
    }
    private List<Tuple<Tuple<int, int>, Tuple<int, int>>> FindOverlaps()
    {
        List<Tuple<Tuple<int, int>, Tuple<int, int>>> overlaps = new List<Tuple<Tuple<int, int>, Tuple<int, int>>>();
        int currentStart = Intervals[0].Item1;
        int currentEnd = Intervals[0].Item2;
        for (int i = 1; i < Intervals.Count; i++)
        {
            int start = Intervals[i].Item1;
            int end = Intervals[i].Item2;
            if (start < currentEnd && currentStart < end)
            {
                overlaps.Add(Tuple.Create(Intervals[i-1], Intervals[i]));
                currentEnd = Math.Max(currentEnd, end);
            }
            else
            {
                currentStart = start;
                currentEnd = end;
            }
        }
        return overlaps;
    }

    private void HandleOverlap(Tuple<Tuple<int, int>, Tuple<int, int>> pair)
    {
        Tuple<int, int> lower = pair.Item1;
        Tuple<int, int> upper = pair.Item2;

        int upperRange = Range(upper);
        int lowerRange = Range(lower);
        Tuple<int, int> temp = Tuple.Create(lower.Item2, lower.Item2 + upperRange);
        if (IsInBound(temp) == 0)
        {
            int idx = Intervals.IndexOf(upper);
            Intervals[idx] = temp;
            foreach (var overlap in FindOverlaps())
                HandleOverlap(overlap);
        }
        else if(IsInBound(temp) < 0)
        {
            int idx = Intervals.IndexOf(upper);
            Intervals[idx] = Tuple.Create(lower.Item2, lower.Item2 + upperRange);
            idx = Intervals.IndexOf(lower);
            Intervals[idx] = Tuple.Create(Boundary.Item1, Boundary.Item1 + lowerRange);
            foreach (var overlap in FindOverlaps())
                HandleOverlap(overlap);
        } 
        else
        {
            int idx = Intervals.IndexOf(upper);
            Intervals[idx] = Tuple.Create(Boundary.Item2 - upperRange, Boundary.Item2);
            idx = Intervals.IndexOf(lower);
            Intervals[idx] = Tuple.Create(upper.Item1 - lowerRange, upper.Item1);
            foreach (var overlap in FindOverlaps())
                HandleOverlap(overlap);
        }
    }
}

迭代版本问题 #

改进后的迭代版本表现更优，但无法处理上边界处的重叠。例如输入[(5,9),(7,10)]、边界(0,10)时，期望输出[(3,7),(7,10)]，实际输出[(5,9),(7,10)]：

public Bookshelf(List<Tuple<int, int>> intervals, Tuple<int, int> boundary)
{
    Intervals = intervals;
    Boundary = boundary;
    HandleOverlap();
}
private void HandleOverlap()
{
    Intervals.Sort((a, b) => a.Item1.CompareTo(b.Item1));
    List<Tuple<int, int>> adjustedIntervals = new List<Tuple<int, int>>();
    int lastEnd = Boundary.Item1;
    foreach (var interval in Intervals)
    {
        int start = interval.Item1;
        int end = interval.Item2;
        if (start < lastEnd)
        {
            start = lastEnd;
            end = start + (interval.Item2 - interval.Item1);
        }
        if (end > Boundary.Item2)
        {
            end = Boundary.Item2;
            start = end - (interval.Item2 - interval.Item1);
        }
        lastEnd = end;
        adjustedIntervals.Add(Tuple.Create(start, end));
    }
    Intervals = adjustedIntervals;
}

可行算法解决方案 #

核心思路 #

要实现最小位移，需保证每个区间的调整幅度尽可能小。正确逻辑为：

1. 先按原始区间的起始位置排序
2. 从左到右遍历调整，确保当前区间起始不小于前一个区间的结束，尽可能贴近原始位置
3. 从右到左遍历调整，确保当前区间结束不大于后一个区间的起始，同时不超出边界上限
4. 两次遍历后，区间既无重叠，又尽可能保留原始位置，且完全处于边界内

伪代码 #

输入：intervals列表，boundary[left, right]
1. 计算总长度sum_length = 所有区间的长度之和
2. 如果sum_length > right - left，抛出异常（空间不足）
3. 将intervals按原始起始位置升序排序
4. 从左到右遍历：
   last_end = left
   for i from 0 to len(intervals)-1:
       interval_len = intervals[i].end - intervals[i].start
       new_start = max(intervals[i].start, last_end)
       new_end = new_start + interval_len
       intervals[i] = [new_start, new_end]
       last_end = new_end
5. 从右到左遍历：
   first_start = right
   for i from len(intervals)-1 down to 0:
       interval_len = intervals[i].end - intervals[i].start
       new_end = min(intervals[i].end, first_start)
       new_start = new_end - interval_len
       intervals[i] = [new_start, new_end]
       first_start = new_start
6. 返回调整后的intervals

C#实现代码 #

public class Bookshelf
{
    public List<Tuple<int, int>> Intervals { get; private set; }
    public Tuple<int, int> Boundary { get; private set; }

    public Bookshelf(List<Tuple<int, int>> intervals, Tuple<int, int> boundary)
    {
        Boundary = boundary;
        int totalLength = intervals.Sum(interval => interval.Item2 - interval.Item1);
        int boundaryLength = boundary.Item2 - boundary.Item1;
        
        if (totalLength > boundaryLength)
            throw new Exception("Not enough space in boundary");

        // 按原始起始位置排序
        Intervals = intervals.OrderBy(interval => interval.Item1).ToList();
        
        // 左到右调整，确保不与前一个重叠，尽可能贴近原始位置
        int lastEnd = boundary.Item1;
        for (int i = 0; i < Intervals.Count; i++)
        {
            int len = Intervals[i].Item2 - Intervals[i].Item1;
            int newStart = Math.Max(Intervals[i].Item1, lastEnd);
            int newEnd = newStart + len;
            Intervals[i] = Tuple.Create(newStart, newEnd);
            lastEnd = newEnd;
        }

        // 右到左调整，确保不与后一个重叠，且不超出边界上限
        int firstStart = boundary.Item2;
        for (int i = Intervals.Count - 1; i >= 0; i--)
        {
            int len = Intervals[i].Item2 - Intervals[i].Item1;
            int newEnd = Math.Min(Intervals[i].Item2, firstStart);
            int newStart = newEnd - len;
            Intervals[i] = Tuple.Create(newStart, newEnd);
            firstStart = newStart;
        }
    }
}

测试验证 #

• 测试输入[(5,9),(7,10)]，边界(0,10)：
  左到右调整后得到[(5,9),(9,13)]，右到左调整时，第二个区间的end设为10，start为10-3=7；第一个区间end设为7，start为7-4=3，最终输出[(3,7),(7,10)]，符合预期。
• 测试示例3输入，调整后结果与示例一致。

内容的提问来源于stack exchange，提问作者Abobobobus