20
\$\begingroup\$

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?
\$\endgroup\$
16
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ You could eliminate all else clauses with a corresponding continue for each one. Some people do not like them though. \$\endgroup\$ – Leonid Feb 9 '17 at 8:58
  • \$\begingroup\$ Wouldn't the max make this O(n2)? \$\endgroup\$ – dan-klasson Nov 21 '18 at 18:48
  • \$\begingroup\$ @dan-klasson max() has two forms: one that just compares two values, and one that scans an entire iterable. Here, the two-argument form is used which effectively completes in constant time, and therefore doesn't affect the algorithmic complexity. \$\endgroup\$ – amon Nov 21 '18 at 18:51
8
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I like this. Why did you name the loop variable iv? What does it stand for? \$\endgroup\$ – Leonid Feb 9 '17 at 9:02
  • \$\begingroup\$ Also, you can probably do: low, high = sorted_intervals.pop(0) so that you do not have to slice the first value off in the for loop construct. \$\endgroup\$ – Leonid Feb 9 '17 at 9:35
  • \$\begingroup\$ While I like "the generator idea", I'd rather use merged_intervals = heapq.heapify(intervals[:]) for an O(n) setup and heapq.heappop(merged_intervals). \$\endgroup\$ – greybeard Apr 23 '18 at 5:49
  • \$\begingroup\$ @greybeard Two things about that: 1) This means you are effectively performing a pure-python mergesort instead of an optimized timsort of the items, and won't be faster; and 2) heapify() does not return the list, but rather operates in-place and returns None. Unless you are only consuming a small, fixed amount of a set of items then using heapify() and heappop() is less good than just sorting. \$\endgroup\$ – Mumbleskates Apr 25 '18 at 4:38
  • \$\begingroup\$ @Mumbleskates: 1) if iterating to the end 2) true about heapify() value; note the [:] for not destroying the input. \$\endgroup\$ – greybeard Apr 25 '18 at 5:09
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ How can you express this in Python in an elegant way? Something like if xs: special_case(xs[0]); for x in xs[1:]: normal_case(x) comes to mind, but that (unlike normal iteration) only works with lists, but not with some iterables such as generators or sets. How would you write it? \$\endgroup\$ – amon Nov 9 '14 at 2:05
  • \$\begingroup\$ @amon Not that I know a generic recipe. It just happened so that the solution was always there. Sorry if I sound poetic. \$\endgroup\$ – vnp Nov 9 '14 at 5:22
  • 1
    \$\begingroup\$ How about invoking the iterable protocol directly: if xs: special_case(next(xs)) ; for x in xs: normal_case(x) \$\endgroup\$ – pjz Nov 10 '14 at 4:07
  • \$\begingroup\$ @pjz: as shown, this seems to handle xs[0] twice; if you don't want that, keep the iterator: if xs: it = xs.__iter__() ; special_case(next(it)) ; for x in it: normal_case(x) (how to do this less ugly?) \$\endgroup\$ – greybeard Nov 24 '16 at 7:32
  • \$\begingroup\$ @greybeard You can capture the first element from an iterator with a for loop over the iterator that immediately breaks, which will simply not assign to the loop variable(s) if the iterable was empty. \$\endgroup\$ – Mumbleskates Apr 25 '18 at 4:59
2
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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]
\$\endgroup\$
-1
\$\begingroup\$

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)])
\$\endgroup\$
  • \$\begingroup\$ At first sight, your code looks ugly. This is because it doesn't follow PEP 8. \$\endgroup\$ – Roland Illig Apr 18 '18 at 5:28
  • \$\begingroup\$ thats fair. I did this to get a quick and workable solution. If you would like to post the more nicely formatted solution the credit is yours \$\endgroup\$ – Alan Shteyman May 9 '18 at 15:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.