合并重叠区间的算法

Question

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

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

变成

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

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

我知道当给出完整数组时，可以在按开始时间升序对间隔进行排序后使用堆栈完成操作（参考：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

现场演示。