Merging Overlapping Intervals

Question

Currently, I have intervals of:

temp_tuple = [[-25, -14], [-21, -16], [-20, -15], [-10, -7], [-8, -5], [-6, -3], [2, 4], [2, 3], [3, 6], [12, 15], [13, 18], [14, 17], [22, 27], [25, 30], [26, 29]]

in an ascending order by the lower bound. My task is to merge overlapping intervals so that the outcome comes out to be:

[-25, -14]
[-10, -3]
[2, 6]
[12, 18]
[22, 30]

My first attempt involved deleting intervals that are completely within previous intervals, like [-21, -16] which falls within [-25, -14]. But deleting objects within a list kept interfering with the loop condition. My second attempt at deleting unnecessary intervals was:

i = 0
j = 1
while i < len(temp_tuples):
    while j < len(temp_tuples):
        if temp_tuples[i][1] > temp_tuples[j][1]:
            del temp_tuples[j]
        j += 1
    i += 1

but this doesn't delete all the unnecessary intervals for some reason. What should I do?

Answer 1

I made some improvements based on vallentin's answer, mainly using copy.deepcopy to prevent any changes to the input.

Note that using sorted() or .copy() is insufficient, as sub-elements get changed when any merge happens.

I also added a .sort() call on each interval to handle unsorted input, as well as a more explicit initial sort call for clarity.

Code:

import copy

def mergeIntervals(input_array, preserve_input=True):
    '''
    Python3 program for merging overlapping intervals.
    If preserve_input is False, the input_array can be modified! Not just sorted, but even sub-elements can change!

    See:
        https://www.educative.io/answers/what-is-the-merge-overlapping-intervals-problem
        https://www.geeksforgeeks.org/merging-intervals/
        https://stackoverflow.com/questions/43600878/merging-overlapping-intervals
    '''
    if preserve_input:
        intervals = copy.deepcopy(input_array)
    else:
        intervals = input_array

    # Sort the given list of time intervals in ascending order of starting time.
    intervals.sort(key=lambda interval: interval[0])

    intervals[0].sort() # deal with unsorted input

    # Create a stack with the first interval
    merged = [intervals[0]]

    for current in intervals[1:]:
        current.sort() # deal with unsorted input
        previous = merged[-1]
        # Check for overlapping interval
        if current[0] <= previous[-1]: # If it’s overlapping, then merge them into one interval;
            previous[-1] = max(previous[-1], current[-1])
        else: # otherwise, push it in the stack.
            merged.append(current)

    return merged

##### Testing code:
A_list = []

# Example from original question:
input_array = [[-25, -14], [-21, -16], [-20, -15], [-10, -7], [-8, -5], [-6, -3], [2, 4], [2, 3], [3, 6], [12, 15], [13, 18], [14, 17], [22, 27], [25, 30], [26, 29]]
A_list.append(input_array)

# Example with unsorted elements and sub-elements:
input_array = [[4, 2], [3, 1]]
A_list.append(input_array)

for preserve_input in [False, True]:
    print(f'==> preserve_input = {preserve_input}')
    for idx, a in enumerate(A_list):
        print('------> idx = ', idx)
        input_array = copy.deepcopy(a)
        print('input before:', input_array)
        output_array = mergeIntervals(input_array, preserve_input=preserve_input)
        print('input after:', input_array)
        print('output', output_array)

        if input_array != a:
            print('Input modified!')
            if preserve_input:
                raise
        else:
            print('No change in input.')

Output:

Note in particular the change of [22, 27] to [22, 30] in the first example, near the end.

==> preserve_input = False
------> idx =  0
input before: [[-25, -14], [-21, -16], [-20, -15], [-10, -7], [-8, -5], [-6, -3], [2, 4], [2, 3], [3, 6], [12, 15], [13, 18], [14, 17], [22, 27], [25, 30], [26, 29]]
input after: [[-25, -14], [-21, -16], [-20, -15], [-10, -3], [-8, -5], [-6, -3], [2, 6], [2, 3], [3, 6], [12, 18], [13, 18], [14, 17], [22, 30], [25, 30], [26, 29]]
output [[-25, -14], [-10, -3], [2, 6], [12, 18], [22, 30]]
Input modified!
------> idx =  1
input before: [[4, 2], [3, 1]]
input after: [[1, 4], [2, 4]]
output [[1, 4]]
Input modified!
==> preserve_input = True
------> idx =  0
input before: [[-25, -14], [-21, -16], [-20, -15], [-10, -7], [-8, -5], [-6, -3], [2, 4], [2, 3], [3, 6], [12, 15], [13, 18], [14, 17], [22, 27], [25, 30], [26, 29]]
input after: [[-25, -14], [-21, -16], [-20, -15], [-10, -7], [-8, -5], [-6, -3], [2, 4], [2, 3], [3, 6], [12, 15], [13, 18], [14, 17], [22, 27], [25, 30], [26, 29]]
output [[-25, -14], [-10, -3], [2, 6], [12, 18], [22, 30]]
No change in input.
------> idx =  1
input before: [[4, 2], [3, 1]]
input after: [[4, 2], [3, 1]]
output [[1, 4]]
No change in input.

Answer 2

#Given an array of intervals in sorted order and a new interval, return a sorted array after merging the interval

def mergeinter(intervals,newinter):
    n = len(intervals)
    start = newinter[0]# we mark the start and end of the new interval to be merged
    end = newinter[1]
    right,left = 0,0
    while right < n:# we track where this new interval belongs, i.e. how many interval are to the left of it and how many are to the right
        if start <= intervals[right][1]:# we find the first interval before which it fits
            if end < intervals[right][0]:# this checks if the interval is disjoint and lies between two given intervals
                break# in this case we have nothing to do and go to line 29 directly
            start = min(start,intervals[right][0])# if it intersects with the given intervals then we just update and merge the ends
            end = max(end,intervals[right][1])
        else:# counting how many to the left continuing from line 20
            left += 1 
        right += 1# moving right to find the fit continuation of line 20 and even if we merge in line 25, we go to the next interval before
    return intervals[:left] + [(start,end)] + intervals[right:] # we return starting from the next interval

#Given a collection of intervals, merge all overlapping intervals and return sorted list of disjoint intervals.

def merge(I):
    I.sort(key:lambda i:i[0])# sorting according to the start of all intervals
    res = []# we start from the last of the given arr of lists and check the ends of the intervals and merge from the end
    for i in I:
        if not res or res[-1][0] < i[1]:# if res is empty then we put an elem in it from I
            res.append(i)# if there is no overlap, just add it
        else:
            res[-1][1] = max(i[1], res[-1][1])# here we merge from the end so that res remains sorted
    return res

Answer 3

This is a numpy solution I came up with:

import numpy as np

def merge_intervals(intervals):
    starts = intervals[:,0]
    ends = np.maximum.accumulate(intervals[:,1])
    valid = np.zeros(len(intervals) + 1, dtype=np.bool)
    valid[0] = True
    valid[-1] = True
    valid[1:-1] = starts[1:] >= ends[:-1]
    return np.vstack((starts[:][valid[:-1]], ends[:][valid[1:]])).T

#example
a=[]
a.append([1,3])
a.append([4,10])
a.append([5,12])
a.append([6,8])
a.append([20,33])
a.append([30,35])

b = np.array(a)

print("intervals")
print(b)
print()
print("merged intervals")
print(merge_intervals(b))

Output:

intervals
[[ 1  3]
 [ 4 10]
 [ 5 12]
 [ 6  8]
 [20 33]
 [30 35]]

merged intervals
[[ 1  3]
 [ 4 12]
 [20 35]]

Please note that the input array must be sorted by start positions.

Answer 4

The salient feature of the solution below is to run a list called final parallel to the input list. Before entering the for loop, the final list inserts the first array item in it. Then starts the comparison. That's it!

def merger(a):

    final=[]

    final.append(a[0])

    for i in range(1,len(a)):

        if a[i][0]<=final[-1][1]:

           if a[i][1]>final[-1][1]:

               low_limit=final[-1][0]
               hi_limit=a[i][1]
               final.pop()
               final.append([low_limit,hi_limit])

           if a[i][1]<=final[-1][1]:

                low_limit=final[-1][0]
                hi_limit=final[-1][1]
                final.pop()
                final.append([low_limit,hi_limit])

          if final[-1][0]<a[i][1]<final[-1][1]:

           low_limit=a[i][0]
           hi_limit=final[-1][1]
           final.pop()
           final.append([low_limit,hi_limit])



        else:
            final.append(a[i])

    return final

if __name__=="__main__":

    array=[[-25, -14], [-21, -16], [-20, -15], [-10, -7], [-8, -5], [-6, -3], [2, 4], [2, 3], [3, 6], [12, 15], [13, 18], [14, 17], [22, 27], [25, 30], [26, 29]]
    print(merger(array))

Output:

[[-25, -14], [-10, -3], [2, 6], [12, 18], [22, 30]]

Answer 5

It makes it a bit easier to process (as in think about) if you instead setup a new list. You additionally also get to keep your original data.

temp_tuple.sort(key=lambda interval: interval[0])
merged = [temp_tuple[0]]
for current in temp_tuple:
    previous = merged[-1]
    if current[0] <= previous[1]:
        previous[1] = max(previous[1], current[1])
    else:
        merged.append(current)

If you now print(merged) it would output:

[[-25, -14], [-10, -3], [2, 6], [12, 18], [22, 30]]