Merging algorithm for 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.

Answer 1

How does the dynamic array matter?

You'll still want to store the values in sorted ascending order. Then it should be a relatively straightforward binary search to find the closest intervals (based on start) then you only need to check one or two intervals to determine overlap (since you can be guaranteed that existing intervals do not overlap).

The challenge you may have is that this approach is not atomic in the least. You'll need to lock the collection while doing the merge, which may not satisfy your frequent update/insert requirements. But by keeping things sorted, you should be able to keep the algorithmic complexity down.