Merging intervals in Python

0
votes

I am very new to Python programming and have come across a problem statement i have no clue how to solve. I have four lines of input:

0 1
2 4
6 7
3 5

For accepting these 4 lines of input i can do the below:

for i in range(4):
    a,b = list(map(int,input().split(' ')))

I am supposed to merge the intervals into(Output) :

0 1
2 5
6 7

Intervals (2,4) and (3,5) they should be merged into one (2,5).

I am not sure how should i go about this ?

Can someone help me in getting a direction?

Thanks in advance.

2
python
What you're expecting as output doesn't seem to have a specific pattern to follow. You would do well by clarifying if there is any (2, 4), (3, 5) = (2, 5) could mean the min and max of the two sets. - chidimo
Yes thanks Parousia , i think that is what this means but there has to be an overlap between two sets. - user1867151
I came up with this (a, b )= min(min((2,4),(3, 5))), max(max((2,4),(3,5))). But there needs to be a more defined pattern. Perhaps more data would help in deciphering such a pattern - chidimo
What have you tried so far? This is a standard problem, here is a question asked in java stackoverflow.com/questions/31670849/… - Hesham Attia

2 Answers

1
votes

Try this

from functools import reduce
# inp = [(0,1),(2,9),(6,7),(3,5)]
inp = [(0,1),(2,4),(6,7),(3,5)]
print(inp)
def merge(li,item):
    if li:
        if li[-1][1] >= item[0]:
            li[-1] = li[-1][0], max(li[-1][1],item[1])
            return li
    li.append(item)
    return li
print(reduce(merge, sorted(inp), []))
3
votes

If you're looking for a Python library that handles intervals arithmetic, consider python-interval. Disclaimer: I'm the maintainer of that library.

import intervals as I

interval = I.empty()
for i, j in [(0, 1), (2, 4), (6, 7), (3, 5)]:
    interval = interval | I.closed(i, j)
print(interval)

results in

[0,1] | [2,5] | [6,7]

See its documentation for more information.