merging intervals repeatedly

[Magdoll]

On Mar 11, 11:01 pm, Dennis Lee Bieber <wlfr... at ix.netcom.com> wrote:
> On Tue, 11 Mar 2008 15:43:40 -0700 (PDT), Magdoll <magd... at gmail.com>
> declaimed the following in comp.lang.python:
>
> > Correct. I meant the final should be
> > (1,30), (29,40), (50,100)
>
>         Actually, even that is incorrect -- note that ,30 overlaps 29,

As someone else pointed out, I can't merge (1,30), (29,40) because N =
5. If N were always 1, I could've easily used IntervalSet to do this
and I would not have to write more than 5 lines total to get this
done. I'm asking precisely because N can be varied and maybe in the
future will be more complex than just an integer.

>
>         Since this feels like a homework assignment, I won't be posting my
> code...

It isn't an homework assignment. I'm writing it for my research. Or
more precisely, I've already written a solution and wanted to see if
any people here know more salient solutions than mine

>
>         I only state that, 1) I did not bother sorting the interval list --
> unless you have very many intervals to process, a simple sequential
> search is probably faster than using bisection/insert algorithm;

Unfortunately that is the case. My input can be more than 1 million
intervals, although they can be further subdivided into smaller lists,
but still, I would be looking at a list of intervals on a size of at
least thousands, so binary search would definitely win over sequential
search.

2) the
> algorithm inserts one interval at a time; 3) merge is accomplished by
> removing/returning the first candidate interval to the insert method,
> computing the min/max of the candidate and input intervals, and
> recursively inserting that new interval -- if there is no candidate
> overlap interval, no interval is returned, and the insert just appends
> the input interval to the list.

This looks like pretty much what my current solution looks like,
except that it's unsorted.