合并重叠间隔的算法

Question

我一直在寻找一种有效的算法来合并重叠间隔的动态数组间。例如，（起始时间，结束时间）明智的，

[(1, 2), (4, 8), (3, 10)]

合并因为（4,8），（3，10）重合之后变为

[(1, 2), (3, 10)]

。重叠意味着两个区间的任何部分共享相同的时刻。

我知道何时给出完整阵列，可以按照开始时间升序（reference: geeksforgeeks）对间隔进行排序后，使用堆栈完成操作。但是这个算法只有在给定的数组是非动态的时候才有效，但是我正在寻找哪一个对于动态数组是有效的。例如，数组间隔将被更新并且频繁插入，并且间隔应该在每个操作上合并。

Answer 1

使用以间隔为起始点的键保留间隔的二叉搜索树（BST）。

对于任何新的间隔插入：

• 发现在BST比新区间的始点小的最大值（可以在O完成（log n）的）。

  该间隔或下一个间隔将与新间隔重叠，或者不会有重叠（在这种情况下，我们只是进行插入）。

• 可能有更多的区间与新区间重叠，因此从这里我们需要遍历BST的其余部分（从上面找到的点开始）并合并具有任何重叠区间的区间。

虽然任何给定的插入可以采取○在最坏的情况下（N log n）的（如果该间隔与例如重叠每隔一个间隔），摊销时间将每个刀片O（log n）的（自我们可以将已完成的工作作为删除元素的一部分，作为插入它的工作的一部分，这是O（log n）工作的总和）。

一些轻测试C++代码这样做：

// set<pair<int, int> > can also be used, but this way seems conceptually simpler 
map<int, pair<int, int> > intervals; 

void insert(int left, int right) 
{ 
    if (!intervals.empty()) 
    { 
    // get the next bigger element 
    auto current = intervals.upper_bound(left); 
    // checking if not found is not needed because of decrement and how C++ iterators work 
    // decrement to get next smaller one instead, but only if we're not that the beginning 
    if (current != intervals.begin()) 
     --current; 
    // skip current if it's entirely to the left of the new interval 
    if (current->second.second < left) 
     ++current; 
    // update new starting point if there's an overlap and current is more to the left 
    if (current != intervals.end() && current->first <= right) 
     left = min(left, current->first); 
    // iterate through while there's an overlap (deleting as we go) 
    for (; current != intervals.end() && current->first <= right; 
      current = intervals.erase(current)) 
     // update the end point of new interval 
     right = max(right, current->second.second); 
    } 
    // insert our updated interval 
    intervals[left] = make_pair(left, right); 
} 

// FYI: current->first is the start, current->second.second is the end 

Live demo。