Merging Overlapping Intervals in Python

Question

I am trying to solve a question wherein overlapping intervals need to be merged: https://leetcode.com/problems/merge-intervals/description/

The question is:

Given a collection of intervals, merge all overlapping intervals.

For example, Given [1,3],[2,6],[8,10],[15,18], return [1,6],[8,10],[15,18].

I tried my solution:

# Definition for an interval.
# class Interval:
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution:
    def merge(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: List[Interval]
        """
        start = sorted([x.start for x in intervals])
        end = sorted([x.end for x in intervals])

        merged = []
        j = 0
        new_start = 0

        for i in range(len(start)):
            if start[i]<end[j]:
                continue
            else:
                j = j + 1
                merged.append([start[new_start], end[j]])
                new_start = i


        return merged

However it is clearly missing the last interval as:

Input : [[1,3],[2,6],[8,10],[15,18]]

Answer :[[1,6],[8,10]]

Expected answer: [[1,6],[8,10],[15,18]]

Not sure how to include the last interval as overlap can only be checked in forward mode.

How to fix my algorithm so that it works till the last slot?

Thanks for your help.

Answer 1

Your code implicitly already assumes the starts and ends to be sorted, so that sort could be left out. To see this, try the following intervals:

intervals = [[3,9],[2,6],[8,10],[15,18]]
start = sorted([x[0] for x in intervals])
end = sorted([x[1] for x in intervals]) #mimicking your start/end lists
merged = []
j = 0
new_start = 0

for i in range(len(start)):
    if start[i]<end[j]:
        continue
    else:
        j = j + 1
        merged.append([start[new_start], end[j]])
        new_start = i
print(merged) #[[2, 9], [8, 10]]

Anyway, the best way to do this is probably recursion, here shown for a list of lists instead of Interval objects.

def recursive_merge(inter, start_index = 0):
    for i in range(start_index, len(inter) - 1):
        if inter[i][1] > inter[i+1][0]:
            new_start = inter[i][0]
            new_end = inter[i+1][1]
            inter[i] = [new_start, new_end]
            del inter[i+1]
            return recursive_merge(inter.copy(), start_index=i)
    return inter    

sorted_on_start = sorted(intervals)
merged = recursive_merge(sorted_on_start.copy())
print(merged) #[[2, 10], [15, 18]]

Answer 2

We can have intervals sorted by the first interval and we can build the merged list in the same interval list by checking the intervals one by one not appending to another one so. we increment i for every interval and interval_index is current interval check

x =[[1,3],[2,6],[8,10],[15,18]]
#y  = [[1,3],[2,6],[8,10],[15,18],[19,25],[20,26],[25,30], [32,40]]

def merge_intervals(intervals):
    sorted_intervals = sorted(intervals, key=lambda x: x[0])
    interval_index = 0
    #print(sorted_intervals)
    for  i in sorted_intervals:

        if i[0] > sorted_intervals[interval_index][1]:
            interval_index += 1
            sorted_intervals[interval_index] = i
        else:
            sorted_intervals[interval_index] = [sorted_intervals[interval_index][0], i[1]]
    #print(sorted_intervals)
    return sorted_intervals[:interval_index+1]

print(merge_intervals(x)) #-->[[1, 6], [8, 10], [15, 18]]
#print ("------------------------------")
#print(merge_intervals(y)) #-->[[1, 6], [8, 10], [15, 18], [19, 30], [32, 40]]

Answer 3

This is very old now, but in case anyone stumbles across this, I thought I'd throw in my two cents, since I wasn't completely happy with the answers above.

I'm going to preface my solution by saying that when I work with intervals, I prefer to convert them to python3 ranges (probably an elegant replacement for your Interval class) because I find them easy to work with. However, you need to remember that ranges are half-open like everything else in Python, so the stop coordinate is not "inside" of the interval. Doesn't matter for my solution, but something to keep in mind.

My own solution:

# Start by converting the intervals to ranges.
my_intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
my_ranges = [range(start, stop) for start, stop in my_intervals]


# Next, define a check which will return True if two ranges overlap.
# The double inequality approach means that your intervals don't
# need to be sorted to compare them.
def overlap(range1, range2):
    if range1.start <= range2.stop and range2.start <= range1.stop:
        return True
    return False


# Finally, the actual function that returns a list of merged ranges.
def merge_range_list(ranges):
    ranges_copy = sorted(ranges.copy(), key=lambda x: x.stop)
    ranges_copy = sorted(ranges_copy, key=lambda x: x.start)
    merged_ranges = []

    while ranges_copy:
        range1 = ranges_copy[0]
        del ranges_copy[0]

        merges = []  # This will store the position of ranges that get merged.

        for i, range2 in enumerate(ranges_copy):
            if overlap(range1, range2):  # Use our premade check function.
                range1 = range(min([range1.start, range2.start]),  # Overwrite with merged range.
                               max([range1.stop, range2.stop]))
                merges.append(i)

        merged_ranges.append(range1)

        # Time to delete the ranges that got merged so we don't use them again.
        # This needs to be done in reverse order so that the index doesn't move.
        for i in reversed(merges):
            del ranges_copy[i]

    return merged_ranges

print(merge_range_list(my_ranges))  # --> [range(1, 6), range(8, 10), range(15, 18)]

Answer 4

Make pairs for every endpoint: (value; kind = +/-1 for start or end of interval)

Sort them by value. In case of tie choose paie with -1 first if you need to merge intervals with coinciding ends like 0-1 and 1-2

Make CurrCount = 0, walk through sorted list, adding kind to CurrCount Start new resulting interval when CurrCount becomes nonzero, finish interval when CurrCount becomes zero.

Answer 5

Late to the party, but here is my solution. I typically find recursion with an invariant easier to conceptualize. In this case, the invariant is that the head is always merged, and the tail is always waiting to be merged, and you compare the last element of head with the first element of tail.

One should definitely use sorted with the key argument rather than using a list comprehension.

Not sure how efficient this is with slicing and concatenating lists.

def _merge(head, tail):
    if tail == []:
        return head

    a, b = head[-1]
    x, y = tail[0]

    do_merge = b > x
    if do_merge:
        head_ = head[:-1] + [(a, max(b, y))]
        tail_ = tail[1:]
        return _merge(head_, tail_)
    else:
        head_ = head + tail[:1]
        tail_ = tail[1:]
        return _merge(head_, tail_)


def merge_intervals(lst):
    if len(lst) <= 1:
        return lst
    lst = sorted(lst, key=lambda x: x[0])
    return _merge(lst[:1], lst[1:])