From: Stefan Lang <perfectly.normal.hacker@...>
Date: 2008-08-07T07:09:35+09:00
Subject: Re: Need help detecting overlapping ranges

2008/8/6 Martin DeMello <martindemello@gmail.com>:
> 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.

It's O(n), but only if you write a radix sort to sort the ranges ;-)

Stefan