From: Martin DeMello <martindemello@...>
Date: 2008-08-07T06:02:21+09:00
Subject: Re: Need help detecting overlapping ranges

On Wed, Aug 6, 2008 at 11:48 AM, Bryan Richardson
<btrichardson@gmail.com> wrote:
> Hello all,
>
> I am writing some code where I create a bunch of ranges, then at the end
> I want to create new ranges out of any ranges that overlap one another.
> For example, say I have the following ranges:
>
> (1..5) (7..11) (22..29) (5..8)
>
> Given the ranges above, I want to end up with the following ranges:
>
> (1..11) (22..29)

Bit busy at work, so I don't have time to play with code, but mostly
your algorithm is slow. This one should work better:

1. sort the array of ranges by startpoint
2. compare the first two ranges. if they overlap, merge them by
setting the second range equal to the merged range and the first to
nil
3. repeat with the next pair, and so on
4. compact the array

in action:

1..5, 5..8, 7..11, 22..29
nil, 1..8, 7..11, 22..29
nil, nil, 1..11, 22..29
no change
1..11, 22..29

Might be some corner cases I haven't taken care of but the basic
algorithm is O(n) and involves no range conversions.

martin