问按间隔合并范围

EN

(我假设这意味着间隔永远不能重叠，否则它们将被合并。)

要做到这一点，一种方法是存储平衡的二进制搜索树，范围的每个端点都有一个节点。然后，每个节点将被标记为标记间隔开始的“开放”节点或标记间隔结束的“关闭”节点。

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

它已经在一个范围内，这意味着您将扩展一个已经存在的范围作为insertion.

• It's的一部分，而不是在范围内，因此您将创建一个新的“”节点。

要确定您所处的情况，您可以在树中对范围的起始点进行前置搜索。如果得到NULL或关闭节点，则需要插入一个新的打开节点来表示范围的起点。如果你得到一个开放的节点，你将继续延长这个时间间隔。

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

1. 您已经查看了树中的所有节点。在这种情况下，您需要插入一个关闭节点来标记此间隔的结束。
2. 您会在范围结束后看到一个关闭节点。在这种情况下，当新的范围结束时，您处于现有范围的中间，所以您不需要做更多的事情。你已经完成了，

，

1. ，你可以在范围结束之前看到一个关闭或打开的节点。在这种情况下，您需要从树中删除该节点，因为旧的范围包含在新的范围中。
2. 您会在范围的末尾看到一个打开的节点。在这种情况下，请在树中插入一个新的关闭节点，因为您需要先终止当前范围，然后才能看到新范围的开始。

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

希望这能有所帮助！

公共类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;   
}

看看这个。它可能会对你有所帮助：- 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