merging intervals repeatedly

[Robert Bossy]

Magdoll wrote:
>> One question you should ask yourself is: do you want all solutions? or
>> just one?
>> If you want just one, there's another question: which one? the one with
>> the most intervals? any one?
>>     
>
> I actually don't know which solution I want, and that's why I keep
> trying different solutions :P
>   
You should think about what is your data and what is probably the "best" 
solution.


>> If you want all of them, then I suggest using prolog rather than python
>> (I hope I won't be flamed for advocating another language here).
>>     
>
> Will I be able to switch between using prolog & python back and forth
> though? Cuz the bulk of my code will still be written in python and
> this is just a very small part of it.
>   
You'll have to popen a prolog interpreter and parse its output. Not very 
sexy.
Moreover if you've never done prolog, well, you should be warned it's a 
"different" language (but still beautiful) with an important learning 
curve. Maybe not worth it for just one single problem.


>> If you have a reasonable number of intervals, you're algorithm seems
>> fine. But it is O(n**2), so in the case you read a lot of intervals and
>> you observe unsatisfying performances, you will have to store the
>> intervals in a cleverer data structure, see one of these:http://en.wikipedia.org/wiki/Interval_treehttp://en.wikipedia.org/wiki/Segment_tree
>>     
>
> Thanks! Both of these look interesting and potentially useful :)
>   
Indeed. However these structures are clearly heavyweight if the number 
of intervals is moderate. I would consider them only if I expected more 
than several thousands of intervals.

Cheers,
RB