合并重叠区间的算法

Question

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

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

变成

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

合并后，因为 (4, 8) 和 (3, 10) 重叠。重叠意味着两个区间的任何部分共享同一时刻。

我知道当给出完整数组时，可以在按开始时间升序对间隔进行排序后使用堆栈完成操作 (reference: geeksforgeeks)。但是这个算法只有在给定数组是非动态的时候才有效，但我正在搜索哪个对动态数组有效。例如，数组区间会频繁更新和插入，每次操作都应合并区间。

Answer 1

保留间隔的二叉搜索树 (BST)，键是间隔的起点。

对于要插入的任何新间隔：

寻找BST中小于新区间起点的最大值（O(log n)即可完成）

那个区间或下一个区间要么与新区间重叠，要么没有重叠（在这种情况下我们只是插入）。
可以有更多的区间与新的区间重叠，所以从这里我们需要迭代BST的其余部分（从上面找到的点开始）并将区间与任何重叠的区间合并.

虽然在最坏的情况下任何给定的插入都可能需要 O(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.

合并重叠区间的算法

Algorithm for merging overlapping intervals

arrays

algorithm

merge

dynamic

intervals