1

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.

Improve this question
1
  • 2
    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?"
    – Eric Lippert
    Commented Jun 21, 2017 at 17:22

1 Answer 1

Reset to default
3

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.

Improve this answer
4
  • Dynamic array matters because for each insert and update I have to do the whole process (the referenced algorithm) which leads into a O(n^2) complexity. I want an efficient algorithm.
    – Sazzad Hissain Khan
    Commented Jun 20, 2017 at 20:48
  • @SazzadHissainKhan - no, you don't. You keep things in order, insert ordered, and it's around O(ln(n))
    – Telastyn
    Commented Jun 20, 2017 at 21:04
  • Its only possible using BST as u suggested, not with array or linked list i guess. I mean O(log(n)).
    – Sazzad Hissain Khan
    Commented Jun 20, 2017 at 21:09
  • @SazzadHissainKhan: With an array or list, finding the insertion point (and check for merge) is still O(log(n)). Making room to insert a new element, or filling a gap created by merging is O(n). If the comparison takes about as many instructions as moving an element, then the overall complexity is O(n).
    – Bart van Ingen Schenau
    Commented Jun 21, 2017 at 8:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.