# Merging algorithm for overlapping intervals

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.

• Don't use an array at all. Construct an interval tree. en.wikipedia.org/wiki/Interval_tree. The interval tree can then efficiently answer questions like "does this interval overlap that interval?" Commented Jun 21, 2017 at 17:22