Merging Overlapping Intervals

Question

A while back I was asked the following question in a phone interview, and to be honest it stumped me. After many long nights of rolling the problem around in my head I think I came up with a decent solution.

The Question:

Given a list of intervals like:

[(5, 7), (11, 116), (3, 6), (10, 12), (6, 12)]

Write a function that will merge overlapping intervals.

My solution:

def merge_intervals(intervals):
    """
    A simple algorithm can be used:
    1. Sort the intervals in increasing order
    2. Push the first interval on the stack
    3. Iterate through intervals and for each one compare current interval
       with the top of the stack and:
       A. If current interval does not overlap, push on to stack
       B. If current interval does overlap, merge both intervals in to one
          and push on to stack
    4. At the end return stack
    """
    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 = tuple([b[0], tup[1]])
                merged.append(new_tup)
            else:
                merged.append(b)
                merged.append(tup)
    return merged

if __name__ == '__main__':

    l = [(5, 7), (11, 116), (3, 4), (10, 12), (6, 12)]
    print("Original list of ranges: {}".format(l))
    merged_list = merge_intervals(l)
    print("List of ranges after merge_ranges: {}".format(merged_list))

My questions are:

1. Run time: Without counting sorting I believe this runs in \$O(n)\$. With counting sorting that would go up to \$O(n*\log(n))\$. Is this correct?
2. Stylistically does anything need to be improved?
3. Is there a more efficient way of solving this problem?

Answer 1

This code has a bug. Consider merge_intervals([(0, 3), (1, 2)]). This returns [(0, 2)] although it should be [(0, 3)]. This can be solved through

new_tup = (b[0], max(b[1], tup[1]))

Your code is nice, and implements the simplest thing that works. However, you might want to work on improving your variable names. Neither l, b, or si are very descriptive, and tup and new_tup unnecessarily refer to their type name rather than their meaning. In contrast, merged is a very clear name. A rewrite of the function body might be:

sorted_by_lower_bound = sorted(intervals, key=lambda tup: tup[0])
merged = []

for higher in sorted_by_lower_bound:
    if not merged:
        merged.append(higher)
    else:
        lower = merged[-1]
        # test for intersection between lower and higher:
        # we know via sorting that lower[0] <= higher[0]
        if higher[0] <= lower[1]:
            upper_bound = max(lower[1], higher[1])
            merged[-1] = (lower[0], upper_bound)  # replace by merged interval
        else:
            merged.append(higher)
return merged

Notice that I decided not to use an explicit tuple(…) constructor – that's mostly useful for converting to tuples from iterables. For tuple literals, you can use the (…, …) syntax.

I also put the comments inside the code, rather than into the docstring. Docstrings are good, but they are intended to explain how to use the function (e.g. what the expected type of parameters is, what the function returns, …). To document implementation details, use normal comments.

You have correctly identified the (average and worst-case) algorithmic complexity as \$O(n \log n)\$. You must consider the sorting. However, best-case complexity is \$O(n)\$, as the Tim Sort used by Python detects already-sorted input.

While your code provides a simple and robust solution, it would be certainly possible to reduce average algorithmic complexity. I expect a kind of self-merging interval tree to have average complexity closer to \$O(n \log m)\$ where \$m\$ is the number of intervals after merging.

Answer 2

This problem is well suited to an iterable method, rather than one that generates a list:

sorted_intervals = sorted(intervals, key=itemgetter(0))

if not sorted_intervals:  # no intervals to merge
    return

# low and high represent the bounds of the current run of merges
low, high = sorted_intervals[0]

for iv in sorted_intervals[1:]:
    if iv[0] <= high:  # new interval overlaps current run
        high = max(high, iv[1])  # merge with the current run
    else:  # current run is over
        yield low, high  # yield accumulated interval
        low, high = iv  # start new run

yield low, high  # end the final run

This hopefully reduces the problem to its simplest concepts. If you are working with tuples that have metadata after index [1], the only thing that needs to change is that low and high must be set separately rather than via a simple unpacking assignment.

Answer 3

This comment is too specific to be a review, yet to long to be a comment. Anyway.

Try to avoid constructs like

for ... :
    if first_iteration:
        special_case_of_first_iteration
    else:
        normal_operations

The special case always can and should be moved out of the loop. Stylistically, it spares one level of indentation. Performance wise, it spares an unnecessary condition test at each iteration.

Answer 4

You are correct in that it is \$O(n \log n)\$ for the sort and \$O(n)\$ for the merging. It adds up to \$O(n \log n)\$.

Stylistically, I don't use Python. But I would use longer variables, sortedIntervals instead of si, lastInterval instead of b, etc.

The only thing I would change is to keep the last interval in a variable instead of adding and removing it from the merged collection.

Answer 5

Version similar to @Widdershins' version but easier to read if you do not know iterable methods. It reuses the sorted array by contracting it merging or copying intervals as needed. Without tuples it gets subtly more compact as s[m] = (s[m][0], t[1]) can become s[m][1] = t[1].

def merge_intervals(intervals):
    s = sorted(intervals, key=lambda t: t[0])
    m = 0
    for  t in s:
        if t[0] > s[m][1]:
            m += 1
            s[m] = t
        else:
            s[m] = (s[m][0], t[1])
    return s[:m+1]

Answer 6

Slight mod to ensure that contiguous intervals are joined. In other words, rather than returning a result like [(1,10),(11,20),(30,40)], return [(1,20),(30,40)]. Change noted in comments.

merged = []

    for higher in sorted_by_lower_bound:
        if not merged:
            merged.append(higher)
        else:
            lower = merged[-1]
            #added this condition branch
            if higher[0] - lower[1] == 1:
                merged[-1] = (lower[0], higher[1])  # replace by merged interval
            #end addition. Also changed if below to elif
            # test for intersection between lower and higher:
            # we know via sorting that lower[0] <= higher[0]
            elif higher[0] <= lower[1]:
                upper_bound = max(lower[1], higher[1])
                merged[-1] = (lower[0], upper_bound)  # replace by merged interval
            else:
                merged.append(higher)
    return merged

Answer 7

This may be a better solution than what is posted above, I even added a unit test:

def compresoneadjtuple(s):
    """useful to compress adjacent entries"""
    if len(s)<1:return s,True
    finals=[]
    for pos in range(len(s)-1):
        firstt, secondt=s[pos],s[pos+1]
        if (firstt[1]==secondt[0]) or (firstt[1]+1==secondt[0]):
            finals.append((firstt[0],secondt[1]))
            finals.extend(s[pos+2:])
            return finals,False
        else:
            finals.append(firstt)
    finals.append(s[-1])
    return finals,True


def merge_intervals(intervals):
    s = sorted(intervals, key=lambda t: t[0])
    m = 0
    for  t in s:
        if t[0] >= s[m][1]:
            m += 1
            s[m] = t
        else:
            s[m] = (s[m][0], t[1])
    done=False
    s=s[:m+1]
    while(not done):
        s,done=compresoneadjtuple(s)
    return s

def testmergeint():
    assert(merge_intervals([])==[])
    assert(merge_intervals([(4,8)])==[(4, 8)])
    assert(merge_intervals([(6,10)])==[(6, 10)])
    assert(merge_intervals([(4,8),(6,10)])==[(4, 10)])
    assert(merge_intervals([(4,8),(6,10),(11,12)])==[(4, 12)])
    assert(merge_intervals([(4,8),(6,10),(11,12),(15,20)])==[(4, 12), (15, 20)])
    assert(merge_intervals([(4,8),(6,10),(11,12),(15,20),(20,25)])==[(4, 12), (15, 25)])