通过边界间隔

Question

I有一个间隔列表和第二个间隔，用于绑定其他间隔。 例如：

[[4,7],[5,7]]
bounded by [0,10]

我需要一种算法，该算法能够以尽可能少的运动移动列表的间隔，以便没有间隔相互重叠，每个间隔都在边界中。

Output: [[4,7],[7,9]]

其他例子：

[[6,8],[6,9]]
bounded by [0,10]
Output: [[5,7],[7,10]]

[[0,1],[5,6],[6,8],[6,9]]
bounded by [0,10]
Output: [[0,1],[4,5],[5,7],[7,10]]

i我试图在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);
        }
    }

如果您知道解决方案，也可以将其写入伪代码。

Edit：
我还尝试了其他方法来解决这个问题。

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;
}

这种方法比我以前的尝试更好。但是，它不能消除上限的重叠。这是我使用的示例

[(5,9),(7,10)] bounded by (0,10)
Expected Output: [(3,7),(7,10)]
Actual Output: [(5,9),(7,10)]

i通过向上移动重叠间隔并检查以后溢出来解决此问题。

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, max = Boundary.Item2;
    foreach (var interval in Intervals)
    {
        int start = interval.Item1;
        int end = interval.Item2;
        if (start < lastEnd)
        {
            start = lastEnd;
            end = start + (interval.Item2 - interval.Item1);
        }
        
        lastEnd = end;
        adjustedIntervals.Add(Tuple.Create(start, end));
    }
    List<Tuple<int, int>> overflows = new List<Tuple<int, int>>();
    int temp = Boundary.Item2;
    for (int i = adjustedIntervals.Count - 1; i > -1; --i)
    {
        if (adjustedIntervals[i].Item2 >= temp)
        {
            int range = adjustedIntervals[i].Item2 - adjustedIntervals[i].Item1;
            overflows.Insert(0, Tuple.Create(temp - range, temp));
            temp -= range;
        }
        else
            overflows.Insert(0, adjustedIntervals[i]);
    }
    Intervals = overflows;
}

Answer 1