CODEWITHSUNDEEP
algorithmbinary-treeinterval-tree
amit
amit

Reputation: 10872

Finding Overlap among multiple intervals

Let's say I have a list of intervals (or ranges) (Eg. 10-15, 5-7, 9-12..). The problem is to find the subset of ranges that overlaps. Of course I can use Interval tree for this.

The actual problem that I have is there are multiple ranges. Best explained by an example:

  1. 10-15, 5-7, 9-12
  2. 1-2, 3-6, 14-15
  3. 3-5, 9-15, 10-15

In the above case, there is an overlap between (1) and (2) at the second range, and between (3) and (1), (2) at third range.

Basically, I need to find all the overlaps between the list of items.

Maybe I can use 3 separate interval trees to find this out. Is there a better way to do this?

Upvotes: 1

Views: 3015

Answers (2)

Devashish Das
Devashish Das

Reputation: 1

Intervals [a0, b0] and [a1, b1] overlap iff min(b1,b0) > max(a1,a0)

Upvotes: -1

Seb
Seb

Reputation: 25147

You could build just one interval tree with all intervals in there. You'll just need to keep track of which range the interval belonged to, such as:

{
  int range;
  int intervalFrom;
  int intervalTo;
}

You can put that structure inside an interval tree and check for overlapping. When you get the problematic intervals, you'll be able to tell which range each one belonged to.

Upvotes: 1

Related Questions