Is a merge interval function available?

Discussion in 'Python' started by Peng Yu, Feb 10, 2010.

  1. Peng Yu

    Peng Yu Guest

    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?
     
    Peng Yu, Feb 10, 2010
    #1
    1. Advertising

  2. 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
     
    Steven D'Aprano, Feb 11, 2010
    #2
    1. Advertising

  3. Peng Yu

    Nobody Guest

    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
     
    Nobody, Feb 11, 2010
    #3
  4. Peng Yu

    Steve Holden Guest

    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/
     
    Steve Holden, Feb 11, 2010
    #4
  5. 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.
     
    Jonathan Gardner, Feb 11, 2010
    #5
  6. * Jonathan Gardner:
    > 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.


    If it's possible, there was/is this guy over in clc.c++ who responded/responds
    to homework questions with the most advanced, convoluted and, except for
    misleading names, technically correct solutions.


    Cheers,

    - Alf
     
    Alf P. Steinbach, Feb 11, 2010
    #6
  7. Peng Yu

    Peter Guest

    On Feb 12, 8:03 am, Jonathan Gardner <>
    wrote:
    > 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.


    Good idea - that would (also) give the teachers a convenient place to
    check for what assignments have been solved by this list so they can
    propose something else.

    They can also grade the submissions against the code kept in this area
    - exact copies could receive an "F" (for example :))

    Peter
     
    Peter, Feb 11, 2010
    #7
  8. Peng Yu

    Nobody Guest

    On Wed, 10 Feb 2010 23:03:29 -0500, Steve Holden wrote:

    >> 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?


    Yes, but I wanted to make it explicit.

    Well, omitting the key= would change the sorting order in the event that
    multiple intervals have the same start, but it still won't affect the
    result of the function overall.
     
    Nobody, Feb 12, 2010
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Dave Varley via .NET 247

    Informix Interval values into a DataGrid

    Dave Varley via .NET 247, Sep 1, 2004, in forum: ASP .Net
    Replies:
    0
    Views:
    684
    Dave Varley via .NET 247
    Sep 1, 2004
  2. New ASP.NET User

    Redirect User to another page after some interval

    New ASP.NET User, Jan 14, 2004, in forum: ASP .Net
    Replies:
    1
    Views:
    511
    Hans Kesting
    Jan 14, 2004
  3. Roland
    Replies:
    1
    Views:
    518
    Rutger Smit
    Sep 8, 2004
  4. Ted Zlatanov

    every($key, $interval) function

    Ted Zlatanov, Jan 8, 2008, in forum: Perl Misc
    Replies:
    17
    Views:
    247
    Ted Zlatanov
    Jan 23, 2008
  5. Peng Yu
    Replies:
    3
    Views:
    124
    Josef
    Feb 14, 2010
Loading...

Share This Page