1

I have a certain amount of intervals, from which I have constructed an interval tree

https://en.wikipedia.org/wiki/Interval_tree

The interval tree is particularly useful for finding an interval overlapping with another certain interval, actually it can do that in O(log N) time.

Now I want to do something more: I want to divide the set of all intervals into a series of disjoint subsets. In every subset each element overlaps with at least another element. An element in a subset does not overlap with an element in a different subset. I call each of these subsets a cluster.

I know a O(N log N) solution, following this nice answer

Possible Interview Question: How to Find All Overlapping Intervals

but I am wondering if, having already created an interval tree, I can use this data structure to create clusters faster.

zakk
  • 375
  • 1
  • 4
  • 14
  • "I want to group all my intervals in clusters of overlapping intervals." - Are you saying, you want ALL intervals that overlap with a given interval `[a, b]`? – kgf3JfUtW Dec 01 '17 at 20:05
  • 1
    Maybe I wasn't clear enough, I'll improve the question. I want to divide all the intervals into overlapping clusters. For instance if I have the following intervals {[1,4], [2,6], [5,7], [8,9]} I want them to be partitioned in two clusters {[1,4], [2,6], [5,7]} and {[8,9]}. – zakk Dec 01 '17 at 21:16
  • 2
    I came up with a better description: I want to divide the set of all intervals into a series of disjoint subsets. In every subset each element overlaps with at least another element. An element in a subset does not overlap with an element in a different subset. – zakk Dec 01 '17 at 21:21
  • For a given node, all intervals stored at that node will be in the same cluster (because they overlap the node's center point). Then you just need to find out if the cluster should be merged with the right-most cluster of the left subtree and the left-most cluster of the right subtree, which can be done with a single comparison each. – Nico Schertler Dec 01 '17 at 21:35

0 Answers0