Is a merge interval function available?

N

Nobody

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
 
S

Steve Holden

Nobody said:
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
 
J

Jonathan Gardner

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.
 
A

Alf P. Steinbach

* Jonathan Gardner:
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
 
P

Peter

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
 
N

Nobody

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.
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top