Алгоритм объединения перекрывающихся интервалов

Держите бинарное дерево поиска (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

Текущая демонстрация.