From: Peng Yu on 10 Feb 2010 18:23 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? From: Steven D'Aprano on 10 Feb 2010 19:26 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) Not in the standard library. There may be third-party libraries that do it. Did you google "python interval"? -- Steven From: Nobody on 10 Feb 2010 22:48 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]) 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 From: Steve Holden on 10 Feb 2010 23:03 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/ From: Jonathan Gardner on 11 Feb 2010 16:03 On Feb 10, 3:23 pm, 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 inhttp://en.wikipedia.org/wiki/Interval_(mathematics)#Excluding_the_end...) > > [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? I vaguely recall a similar question a long time ago. Peng, is this a homework assignment? Perhaps we should add a standard module called "homework". It can have functions for all the different homework assignments we see on c.l.python. We can simply point people to this module and then can include the code in their answers.