Finding Overlap among multiple intervals

Question

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?

Answer 1

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.