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)]
[(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.