Hi Knut, my problem at hand can be defined as follows:I start of with a set of intervals. That is a set of pairs of integers defining the interval start and end point. This two integers do not necessarily span the same range in all the intervals in the set.
I then like to merge all overlapping/intersecting intervals. This may be done on the fly while constructing a new data structure.
It looks as if the IntervalTree would be the perfect datastructure to use since its storing the current sets of (non-overlapping) intervals which can be easily queried given the new interval to be added.
If the query interval overlaps one or potentially several intervals stored in the Tree all of them should be merged to obtain the spanning Interval (union of all intervals overlapping the query one).
It should be straightforward to simply remove the set of overlapping intervals from the IntervalTree and then add the spanning Interval.
According to wiki deletion of nodes from an interval tree may be tricky but should be possible
I was wondering if I'm mistaken or if there is another straightforward way I'm not aware of.
Thanks a lot! Best, Fabian Knut Reinert wrote:
Dear Fabian, your problem is not yet well posed. Currently, an obvious solution (which you probably will not like) is to create a single interval using the overall minimum and maximum coordinate of your intervals. Can you elaborate more on your problem? Knut On Sep 16, 2010, at 7:00 AM, Fabian Buske wrote:I like to merge a bunch of intervals in case they overlap such that in the end any single point will be covered by at most interval.
-- Fabian Buske Institute for Molecular BioscienceThe University of Queensland Brisbane, Qld. 4072 Australia