On Mar 11, 11:01 pm, Dennis Lee Bieber <[EMAIL PROTECTED]> wrote: > On Tue, 11 Mar 2008 15:43:40 -0700 (PDT), Magdoll <[EMAIL PROTECTED]> > 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. -- http://mail.python.org/mailman/listinfo/python-list
