10

给定一组区间：{1-4, 6-7, 10-12} 添加一个新区间：(9,11)，以便最终解决方案“合并”：输出：{1-4, 6-7, 9-12}。合并可以发生在双方（低范围和高范围）。

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

如果有人可以帮助我理解我们如何在这个用例中使用区间树，那就太好了！

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

4

5 回答 5

7

（我假设这意味着间隔永远不会重叠，否则它们会被合并。）

一种方法是存储平衡的二叉搜索树，每个范围的端点有一个节点。然后将每个节点标记为标记间隔开始的“打开”节点或标记间隔结束的“关闭”节点。

插入新范围时，将出现关于范围起点的两种情况之一：

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

要确定您所处的情况，您可以在树中进行先行搜索以查找范围的起点。如果您获得 NULL 或关闭节点，则需要插入一个表示范围起点的新打开节点。如果您获得一个开放节点，您将继续延长该间隔。

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

  1. 您已经查看了树中的所有节点。在这种情况下，您需要插入一个关闭节点来标记此间隔的结束。

  2. 您会在范围结束后看到一个关闭节点。在这种情况下，当新范围结束时，您处于现有范围的中间，因此您无需再做任何事情。你完成了。

  3. 您会在范围结束之前看到一个关闭或打开的节点。在这种情况下，您需要从树中删除该节点，因为旧范围已被新范围包含。

  4. 您会在范围结束后看到一个打开的节点。在这种情况下，将一个新的关闭节点插入树中，因为您需要在看到这个新节点的开始之前终止当前范围。

天真地实现，该算法的运行时间为 O(log n + k log n)，其中 n 是间隔数，k 是在此过程中删除的间隔数（因为您必须执行 n 次删除）。但是，您可以使用以下技巧将其加速到 O(log n)。由于删除过程总是按顺序删除节点，因此您可以使用后继搜索端点来确定要删除的范围的末尾。然后，您可以通过执行两个树拆分操作和一个树连接操作来拼接子范围以从树中删除。在合适的平衡树（例如红黑树或 splay）上，这可以在 O(log n) 总时间内完成，如果要包含很多范围，这会快得多。

希望这可以帮助！

于 2013-01-27T09:01:55.120 回答
1

公共类 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;   
}
于 2015-10-08T22:20:18.730 回答
0

看一下这个。它可以帮助你：- http://www.boost.org/doc/libs/1_46_0/libs/icl/doc/html/index.html

该库提供以下功能：

1) 间隔集

2) 分离间隔集

3) split_interval_set

于 2013-01-27T08:32:24.820 回答
0

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);
    }
}
于 2017-08-07T19:22:16.420 回答
-1

这只需将相关区间添加到区间集的末尾，然后对区间集的所有元素执行合并即可。

合并操作在这里很详细： 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

不要忘记你的鼻子测试来验证你确实做了正确的工作：

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}]
于 2013-09-20T21:04:37.480 回答