合并区间范围

Question

给定一个区间集合：{1-4，6-7，10-12}，添加一个新的区间：(9,11)，使最终解决方案“合并”，输出为：{1-4，6-7，9-12}。合并可以在两个端点（低范围和高范围）上进行。

我看到这个问题在多个地方得到了回答，甚至有人建议使用区间树，但没有解释他们如何使用它。我所知道的唯一解决方案是按照它们的开始时间升序排列区间，并在迭代它们时尝试适当地合并它们。

如果有人能帮助我理解如何在这种情况下使用区间树，那就太棒了！

[我一直在关注CLRS书中的区间树，但他们并没有讨论合并，他们只谈论插入和搜索]

- Darth.Vader

---

这个回答：https://dev59.com/zGw15IYBdhLWcg3wqNqM#6462731提到了合并区间树的算法。 - vvladymyrov

Answer 1

我假设这意味着区间永远不会重叠，否则它们将被合并。一种方法是使用平衡二叉搜索树存储范围的每个端点一个节点。然后每个节点都标记为“开放”节点表示区间的开始或“关闭”节点表示区间的结束。

插入新区间时，关于范围起点会发生两种情况之一：

1. 它已经在一个区间内，这意味着您将作为插入的一部分扩展已经存在的区间。 2. 它不在任何区间内，因此您将创建一个新的“开放”节点。

要确定您处于哪种情况，请在树中对范围起点进行前驱搜索。如果您获得NULL或关闭节点，则需要插入一个新的打开节点表示范围的起点。如果您获得打开节点，则只需继续扩展该区间。

从那里，您需要确定范围延伸多远。为此，请连续计算插入的初始节点的后继，直到发生以下情况之一：

1. 您查看了树中的所有节点。在这种情况下，您需要插入一个关闭节点，表示此间隔的结束。 2. 在范围结束后，您会看到一个关闭节点。在这种情况下，当新范围结束时，您处于现有范围的中间，因此不需要执行任何其他操作。你完成了。 3. 在范围结束之前，您会看到一个关闭或打开节点。在这种情况下，您需要从树中删除该节点，因为旧区间被新区间包含。 4. 您会在范围结束后看到一个打开节点。在这种情况下，请插入一个新的关闭节点到树中，因为在查看此新节点的开始之前，您需要终止当前区间。

实现简单的情况下，此算法的运行时间为O（log n + k log n），其中n是区间的数量，k是在此过程中删除的区间数（因为您必须执行n次删除）。但是，您可以通过使用以下技巧将其加速到O（log n）。由于删除过程总是按顺序删除节点，因此可以使用后继搜索端点来确定要删除的范围的末尾。然后，您可以通过执行两个树分裂操作和一个树合并操作将要删除的子范围从树中剪切出来。在适当的平衡树（例如红黑树或伸展树）上，可以在总时间内以O（log n）的时间完成此操作，如果许多范围将被包含，则速度更快。

希望这可以帮助！

- templatetypedef

---

对于起始点插入情况：首先在查找前任节点之前，您需要检查是否存在具有相同值的节点。如果存在且为“开放”节点，则无需进行任何操作即可完成（对于起始点不做任何处理）。如果它是一个“关闭”节点，则需要删除该节点（区间正在被扩展）。 - Martijn Pieters

Answer 2

公共类 MergeIntervals {

public static class Interval {

    public double start;
    public double end;

    public Interval(double start, double end){
        this.start = start;
        this.end = end;
    }
}

public static List<Interval> mergeInteval(List<Interval> nonOverlapInt, Interval another){

    List<Interval> merge = new ArrayList<>();

    for (Interval current : nonOverlapInt){

        if(current.end < another.start || another.end < current.start){
            merge.add(current);
        }
        else{

            another.start = current.start < another.start ? current.start : another.start ;
            another.end = current.end < another.end ? another.end : current.end;                
        }           
    }
    merge.add(another);
    return merge;   
}

- Gökhan Akduğan

Answer 3

看看这个。它可能对你有帮助: - http://www.boost.org/doc/libs/1_46_0/libs/icl/doc/html/index.html

这个库提供了以下功能：

1）interval_set

2）separate_interval_set

3）split_interval_set

- Rahul Tripathi

---

谢谢，但我更感兴趣的是算法，而不是现成的库/ API。 - Darth.Vader

一个简单的算法可以是，首先按起始值对范围进行排序，然后从开头到结尾迭代范围，每当您发现一个与下一个重叠的范围时，就将它们合并。 - Rahul Tripathi

是的，我已经知道了。引用我的问题：“我所知道的唯一解决方法是将间隔按其开始时间升序排列，并在其上进行迭代，尝试适当地合并它们。”。我正在寻找更优的解决方案（可能涉及区间树）？ - Darth.Vader

Answer 4

C#

public class Interval
{
    public Interval(int start, int end) { this.start = start; this.end = end; }
    public int start;
    public int end;
}

void AddInterval(List<Interval> list, Interval interval)
{
    int lo = 0;
    int hi = 0;
    for (lo = 0; lo < list.Count; lo++)
    {
        if (interval.start < list[lo].start)
        {
            list.Insert(lo, interval);
            hi++;
            break;
        }
        if (interval.start >= list[lo].start && interval.start <= list[lo].end)
        {
            break;
        }
    }
    if (lo == list.Count)
    {
        list.Add(interval);
        return;
    }

    for (hi = hi + lo; hi < list.Count; hi++)
    {
        if (interval.end < list[hi].start)
        {
            hi--;
            break;
        }
        if (interval.end >= list[hi].start && interval.end <= list[hi].end)
        {
            break;
        }
    }
    if (hi == list.Count)
    {
        hi = list.Count - 1;
    }

    list[lo].start = Math.Min(interval.start, list[lo].start);
    list[lo].end = Math.Max(interval.end, list[hi].end);

    if (hi - lo > 0)
    {
        list.RemoveRange(lo + 1, hi - lo);
    }
}

- user7431997

Answer 5

这可以通过将所需间隔添加到间隔集的末尾，然后对间隔集的所有元素执行合并来简单完成。

合并操作在此处有详细说明：http://www.geeksforgeeks.org/merging-intervals/

如果您不想使用C++代码，这里是相同的Python代码：

def mergeIntervals(self, intervalSet):
    # interval set is an array.
    # each interval is a dict w/ keys: startTime, endTime.  
    # algorithm from: http://www.geeksforgeeks.org/merging-intervals/
    import copy
    intArray = copy.copy(intervalSet)
    if len(intArray) <= 1:
        return intArray
    intArray.sort(key=lambda x: x.get('startTime'))
    print "sorted array: %s" % (intArray)
    myStack = []  #append and pop.
    myStack.append(intArray[0])
    for i in range(1, len(intArray)):
        top = myStack[0]
        # if current interval NOT overlapping with stack top, push it on.
        if   (top['endTime'] < intArray[i]['startTime']):
            myStack.append(intArray[i])
        # otherwise, if end of current is more, update top's endTime
        elif (top['endTime'] < intArray[i]['endTime']):
            top['endTime'] = intArray[i]['endTime']
            myStack.pop()
            myStack.append(top)

    print "merged array: %s" % (myStack)
    return myStack

不要忘记运行nosetests来验证您是否正确地完成了工作：

class TestMyStuff(unittest.TestCase):

    def test_mergeIntervals(self):
        t = [ { 'startTime' : 33, 'endTime' : 35 }, { 'startTime' : 11, 'endTime' : 15  }, { 'startTime' : 72, 'endTime' : 76 }, { 'startTime' : 44, 'endTime' : 46  } ]
        mgs = MyClassWithMergeIntervalsMethod()
        res = mgs.mergeIntervals(t)
        assert res == [ { 'startTime' : 11, 'endTime' : 15  }, { 'startTime' : 33, 'endTime' : 35 }, { 'startTime' : 44, 'endTime' : 46  }, { 'startTime' : 72, 'endTime' : 76 } ]

        t = [ { 'startTime' : 33, 'endTime' : 36 }, { 'startTime' : 11, 'endTime' : 35  }, { 'startTime' : 72, 'endTime' : 76 }, { 'startTime' : 44, 'endTime' : 46  } ]
        mgs = MyClassWithMergeIntervalsMethod()
        res = mgs.mergeIntervals(t)
        assert res == [{'endTime': 36, 'startTime': 11}, {'endTime': 46, 'startTime': 44}, {'endTime': 76, 'startTime': 72}]

- Kevin J. Rice