Is a merge interval function available?

Steve Holden steve at holdenweb.com
Thu Feb 11 05:03:29 CET 2010


Nobody wrote:
> On Wed, 10 Feb 2010 15:23:42 -0800, Peng Yu wrote:
> 
>> I'm wondering there is already a function in python library that can
>> merge intervals. For example, if I have the following intervals ('['
>> and ']' means closed interval as in
>> http://en.wikipedia.org/wiki/Interval_(mathematics)#Excluding_the_endpoints)
>>
>> [1, 3]
>> [2, 9]
>> [10,13]
>> [11,12]
>>
>> I want to get the following merged intervals.
>>
>> [1,9]
>> [10,13]
>>
>> Could somebody let me know if there is a function in the python
>> library?
> 
> No, but try this:
> 
> def merge(intervals):
>     if not intervals:
> 	return []
>     intervals = sorted(intervals, key = lambda x: x[0])

Since Python uses lexical sorting and the intervals are lists isn't the
key specification redundant here?

>     result = []
>     (a, b) = intervals[0]
>     for (x, y) in intervals[1:]:
> 	if x <= b:
> 	    b = max(b, y)
> 	else:
> 	    result.append((a, b))
> 	    (a, b) = (x, y)
>     result.append((a, b))
>     return result
> 
regards
 Steve
-- 
Steve Holden           +1 571 484 6266   +1 800 494 3119
PyCon is coming! Atlanta, Feb 2010  http://us.pycon.org/
Holden Web LLC                 http://www.holdenweb.com/
UPCOMING EVENTS:        http://holdenweb.eventbrite.com/




More information about the Python-list mailing list