Algorithm for merging overlapping intervals

Question

I have been searching for an efficient algorithm to merge overlapping intervals on a dynamic array of intervals. For example, (start time, end time) wise,

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

becomes

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

after merging because (4, 8) and (3, 10) are overlapped. Overlapping means any part of the two intervals share the same moment.

I know when a full array is given the operation can be done with a stack after sorting the intervals on start time ascending order (reference: geeksforgeeks). But this algorithm is effectively applicable only when given array is non dynamic, but I am searching which will be efficient for dynamic array. For example, array intervals will be updated and inserted frequently and intervals should be merged on each operation.

Presley

If you array is always "merged" and sorted, the complexity of adding a new interval should be O(log n) (as for binary search of the appropriate place to insert/merge). – Physic

Can you please elaborate the full algorithm on answer section. @EugeneSh. – Presley

Answer 1

Keep a binary search tree (BST) of intervals with the key being the starting point of the interval.

For any new interval to be inserted:

• Find the biggest value in the BST smaller than the starting point of the new interval (can be done in O(log n)).

  Either that interval or the next interval will overlap with the new interval, or there will be no overlap (in which case we just do an insert).

• There can be more intervals overlapping with the new interval, so from here we need to iterate through the rest of the BST (starting from the point found above) and merge the interval with any overlapping intervals.

While any given insert can take O(n log n) in the worst case (in case that interval overlaps with e.g. every other interval), the amortised time will be O(log n) per insert (since we can count the work done to delete an element as part of the work done to insert it, which is O(log n) work in total).

Some lightly-tested C++ code doing this:

// 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.

Androecium