How to merge overlapping intervals in Python

Question

It should be a function that should simplify the output of the information. For instance, the input is a list of tuples [(2, 7), (7, 8)] then the output should be [(2, 8)]

I have tried to solve this task but there is somewhere a mistake or perhaps my approach to this problem is incorrect

def func(array):
    temparray = []
    for i in range(len(array) - 1):
        if math.fabs(array[i + 1][0] - array[i][1]) == 0 or math.fabs(array[i + 1][0] - array[i][1]) == 1:
            if array[i + 1][1] > array[i][1]:
                temparray.append(tuple([array[i][0], array[i + 1][1]]))
            else:
                temparray.append(tuple([array[i][0], array[i][1]]))
        else:
            temparray.append(tuple([array[i][0], array[i][1]]))
    return temparray

I expect the output of [(3, 5), (4, 8), (10, 12), (9, 10)] to be [(3, 8), (9, 12)], but the actual output is [(3, 8), (4, 8), (10, 12)].

here is the solution:

def func(intervals):
    si = sorted(intervals, key=lambda tup: tup[0])
    merged = []

    for tup in si:
        if not merged:
            merged.append(tup)
        else:
            b = merged.pop()
            if b[1] >= tup[0]:
                new_tup = (b[0], max(b[1], tup[1]))
                merged.append(new_tup)
            else:
                merged.append(b)
                merged.append(tup)
    return merged

For more details -> https://codereview.stackexchange.com/questions/69242/merging-overlapping-intervals

should this boil down as much as possible, or only ever a merge of two? for instance `[ (1,2), (3,2), (3,4) ] -> [ (1,4) ]`? And what about this? `[ (1,2), (1,2) ] -> [ () ]`? Or this? `[ (1,2), (2,3), (2,4) ] -> ???` — nnolte, Jul 06 '19 at 13:57
You are *merging overlapping intervals*, see [Merging Overlapping Intervals python](//stackoverflow.com/q/43600878) — Martijn Pieters, Jul 06 '19 at 14:00
so we need to reduce as much as possible. [(1,2), (3,2), (3,4)] -> [(1,4)] [(1,2), (1,2)] -> [(1,2)] [(1,2), (2,3), (2,4)] -> [(1,4)] — SkyLexxX, Jul 06 '19 at 14:03
No need to use `math.fabs()` here, you are working with integers only. See [Python - abs vs fabs](//stackoverflow.com/q/10772302). In fact, you don't want to use absolute differences **at all**. — Martijn Pieters, Jul 06 '19 at 14:03
For example, the absolute difference between the last and first elements of `(..., 12), (9, ...)` is not 0 or 1, but you'd want to merge those anyway. You want to merge when the start value of the next interval is equal or lower to the end value of the current, `array[i + 1][0] <= array[i][1]`. You also don't handle skipping intervals that have already been absorbed. — Martijn Pieters, Jul 06 '19 at 14:04

Smart Manoj · Answer 1 · 2019-07-06T15:19:58.953

If you use temp array you can't reduce as much as possible.

def func(array):
    l=len(array)
    for i in range(1,l):
        check=False
        check=array[i-1] and abs(array[i][0] - array[i-1][1]) <=1
        if not check and array[i-1] and abs(array[i][1] - array[i-1][0]) <=1:
            array[i-1],array[i]=array[i],array[i-1]
            check=True
        if check:
            if array[i][1] > array[i-1][1]:
                array[i]=(array[i-1][0], array[i][1])
            else:
                array[i]=array[i-1]
            array[i-1]=None
    return [i for i in array if i]


assert func([(3, 5), (4, 8), (10, 12),(9, 10),]) == [(3, 8), (9, 12)]
assert func([(1,2), (3,2), (3,4)]) == [(1,4)]
assert func([(1,2), (1,2)]) == [(1,2)]
assert func([(1,2), (2,3), (2,4)]) == [(1,4)]

How to merge overlapping intervals in Python

1 Answers1