# Merging Overlapping Intervals

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)
merged = []

for tup in si:
if not merged:
merged.append(tup)
else:
b = merged.pop()
if b >= tup:
new_tup = tuple([b, tup])
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?

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, max(b, tup))


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)
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 <= higher
if higher <= lower:
upper_bound = max(lower, higher)
merged[-1] = (lower, 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.

• You could eliminate all else clauses with a corresponding continue for each one. Some people do not like them though. Feb 9 '17 at 8:58
• Wouldn't the max make this O(n2)? Nov 21 '18 at 18:48
• @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.
– amon
Nov 21 '18 at 18:51

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

for iv in sorted_intervals[1:]:
if iv <= high:  # new interval overlaps current run
high = max(high, iv)  # 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 , the only thing that needs to change is that low and high must be set separately rather than via a simple unpacking assignment.

• I like this. Why did you name the loop variable iv? What does it stand for? Feb 9 '17 at 9:02
• 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. Feb 9 '17 at 9:35
• 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). Apr 23 '18 at 5:49
• @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. Apr 25 '18 at 4:38
• @Mumbleskates: 1) if iterating to the end 2) true about heapify() value; note the [:] for not destroying the input. Apr 25 '18 at 5:09

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.

• How can you express this in Python in an elegant way? Something like if xs: special_case(xs); 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?
– amon
Nov 9 '14 at 2:05
• @amon Not that I know a generic recipe. It just happened so that the solution was always there. Sorry if I sound poetic.
– vnp
Nov 9 '14 at 5:22
• How about invoking the iterable protocol directly: if xs: special_case(next(xs)) ; for x in xs: normal_case(x)
– pjz
Nov 10 '14 at 4:07
• @pjz: as shown, this seems to handle xs 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?) Nov 24 '16 at 7:32
• @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. Apr 25 '18 at 4:59

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.

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], t) can become s[m] = t.

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


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]
if higher - lower == 1:
merged[-1] = (lower, higher)  # 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 <= higher
elif higher <= lower:
upper_bound = max(lower, higher)
merged[-1] = (lower, upper_bound)  # replace by merged interval
else:
merged.append(higher)
return merged


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

def compresoneadjtuple(s):
if len(s)<1:return s,True
finals=[]
for pos in range(len(s)-1):
firstt, secondt=s[pos],s[pos+1]
if (firstt==secondt) or (firstt+1==secondt):
finals.append((firstt,secondt))
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)
m = 0
for  t in s:
if t >= s[m]:
m += 1
s[m] = t
else:
s[m] = (s[m], t)
done=False
s=s[:m+1]
while(not done):