Merging intervals in Python

Why this matters

Many real lists are made of ranges. A calendar has meetings that start at one time and end at another. A hotel has bookings for nights. A log file has time spans during which a server was busy. Often the ranges overlap or touch, and you want the shortest list that covers the same time. Two meetings that overlap should be shown as one block of busy time, not two blocks drawn on top of each other.

This is the merging intervals problem. It is a standard interview question, and it is a good first example of a divide and conquer step: the work is split into a sort, such as merge sort, which is a divide and conquer method, and then one simple pass over the sorted list. The sort is covered in the sorting lessons, and the general idea of splitting a problem is covered in the first lesson of this module. This lesson only needs the fact that sorting a list of n items costs about n log n steps, where log n is how many times n can be halved before it reaches 1.

What an interval is

An interval is a pair of numbers, a start and an end. In Python, a common way to store one interval is a list with two numbers, such as [1, 3]. The start is iv[0] and the end is iv[1]. Python counts positions in a list from 0, so iv[0] is the first item. A list of intervals is a list of these small lists, such as [[1, 3], [2, 6]].

This lesson uses lists, which can be changed after they are made. The scan changes the end of a block, and one of the common mistakes below comes from that change. A tuple, written (1, 3), cannot be changed, so it avoids that mistake, but the scan then has to build a new tuple for each change.

This lesson treats intervals as closed. That means the start and the end both belong to the interval. The interval [1, 3] covers the points 1, 2 and 3, and every point in between if the numbers are real numbers. Because the end is included, two intervals that only touch at one point do overlap. For example, [1, 2] and [2, 3] share the point 2, so they merge into [1, 3]. If your problem treats touching intervals as separate, the check in the code must change, as covered in the common mistakes section.

The problem in plain words

You are given a list of intervals. Some may overlap, some may touch, and some may sit inside others. Return the shortest list of intervals that covers the same points, with no two intervals overlapping. The list you return should be in order by start.

A small example makes this concrete. Take the list [1, 3], [2, 6], [8, 10] and [15, 18]. The first two overlap, because [2, 6] starts before [1, 3] ends. The other two stand alone. The answer is [1, 6], [8, 10] and [15, 18]. Three intervals are left after four were given.

Why sorting comes first

Suppose the intervals are already in order by start. Then an overlap can only happen between an interval and the one just after it in the list. You never need to look further, because a later interval starts even later, so it cannot reach back to an earlier interval.

If the list is not sorted, that promise is gone. Take [8, 10], [1, 3] and [2, 6]. The correct answer is [1, 6] and [8, 10]. Now look at what a naive scan does, which compares each interval only with the current block and never sorts. It starts with [8, 10], then sees [1, 3]. Since 1 is not after 10, the scan treats them as one block and makes [8, 10] the current block. Then [2, 6] also falls inside, and the answer comes out as [8, 10] alone. The interval [1, 6] disappears.

Sorting by start fixes this. After sorting, the list becomes [1, 3], [2, 6], [8, 10], and the scan works.

Python's sorted() returns a new sorted list and leaves the list it was given unchanged. Its key argument says what to compare by. The value lambda iv: iv[0] is a small unnamed function, called a lambda. Python calls it on each interval, gets the start back, and sorts by those starts.

The one-pass scan

After sorting, walk through the list once and keep one block called current. It starts as the first interval. For each next interval, there are two cases.

Case 1, the next interval starts after current ends. Then they do not overlap. Save current in the output list, and make the next interval the new current.

Case 2, the next interval starts at or before the end of current. Then they overlap or touch. Extend current so that its end is the larger of the two ends.

The larger end matters. Suppose current is [1, 10] and the next interval is [2, 3]. The next interval ends at 3, which is before 10. If the code replaced the end with 3, the block would shrink to [1, 3] and lose the time from 3 to 10. The built-in max function keeps the correct end.

When the loop ends, the last current has not been saved yet. It must be added to the output after the loop.

A worked example by hand

Here is the first example, step by step. The sorted list is already in order, so the sort changes nothing.

At step 1 the end changes from 3 to 6, because 6 is larger. At steps 2 and 3 the scan saves the old block and starts a new one. After the loop, the last block is added.

A harder example with single points

The third example in the program has intervals that are only a single point. Sorting by start gives the list [1, 4], [4, 4], [5, 5], [6, 8], [7, 9]. All five starts are different, so the sorted order is fixed.

Step 1 shows the touching rule in action. The interval [4, 4] starts exactly where [1, 4] ends, so the end stays at 4. Step 3 shows a one-point interval staying on its own: the next interval starts at 6, which is after 5. Step 4 extends [6, 8] to [6, 9], since 9 is larger than 8.

The full program

The program below sorts a copy of the input, runs the scan, and prints results for several inputs. It does not change the lists passed in. sorted returns a new list, list(ordered[0]) makes a copy of the first interval, and the scan creates a new list for every block it saves.

The output is:

first:    [[1, 6], [8, 10], [15, 18]]
second:   [[1, 10]]
third:    [[1, 4], [5, 5], [6, 9]]
touching: [[1, 3]]
empty:    []
input:    [[1, 3], [2, 6], [8, 10], [15, 18]]

The second example shows one interval inside another. The intervals [2, 3] and [4, 5] both sit inside [1, 10], so the answer is only [1, 10]. The third example has duplicates and unsorted input. After sorting by start, the list is [1, 4], [4, 4], [5, 5], [6, 8], [7, 9]. The first two touch, so they join into [1, 4]. Then [5, 5] starts after [1, 4] ends, so it stands alone. Then [6, 8] and [7, 9] overlap, so they join into [6, 9].

The last line of output confirms that the input list is unchanged. The sorted list holds the same inner lists, but the scan never changes them.

The cost

The sort takes about n log n steps for n intervals. The scan after it looks at each interval once, so it takes about n steps. The total is dominated by the sort. The output list can be as long as the input, so the extra memory is about n intervals in the worst case, when none of them overlap.

Python's sorted uses a merge-based method called Timsort. Merge-based sorts split the list in halves, sort each half, and merge them back, which is a divide and conquer method. The merging interval problem therefore uses divide and conquer inside its sort, and then a simple linear scan.

Common mistakes

Forgetting to sort

Without a sort, the scan can miss overlaps, as shown above. The program below runs the same scan on the list [8, 10], [1, 3], [2, 6] without the sort step.

The output is:

no sort: [[8, 10]]

The correct answer is [[1, 6], [8, 10]]. Any input that is not already sorted can give a wrong answer. The error is quiet, so the program does not stop, and the output only looks wrong to someone who checks it.

Replacing the end instead of taking the maximum

The line current[1] = end looks like the same idea, but it is wrong. The program below uses this line on the second example.

The output is:

replace end: [[1, 3], [4, 5]]

The interval [4, 5] starts inside [1, 10], so the right answer is [[1, 10]]. The end of current must be the largest end seen so far, which is what max gives.

Forgetting the last interval

The scan saves an interval only when it meets an interval that starts later. The last block never meets a later one, so it is saved only by the line after the loop. The program below leaves out merged.append(current) after the loop.

The output is:

no last add: [[1, 6], [8, 10]]

The interval [15, 18] is lost. The fix is the line merged.append(current) after the loop.

Passing a flat list instead of a list of pairs

The function expects a list of pairs, such as [[1, 3], [2, 6]]. If you pass a flat list of numbers, [1, 3, 2, 6], the sort key tries to read iv[0] from the number 1. Numbers cannot be indexed, so Python stops with this error:

Traceback (most recent call last):
  File ".../s13_5.py", line 18, in <module>
    print(merge([1, 3, 2, 6]))
          ~~~~~^^^^^^^^^^^^^^^
  File ".../s13_5.py", line 4, in merge
    ordered = sorted(intervals, key=lambda iv: iv[0])
  File ".../s13_5.py", line 4, in <lambda>
    ordered = sorted(intervals, key=lambda iv: iv[0])
                                               ~~^^^
TypeError: 'int' object is not subscriptable

The path lines show where the file was saved, so they will differ on your machine. The last line names the problem: 'int' object is not subscriptable means you tried to use [0] on a plain number. The fix is to check the shape of the input, or to make sure each item is a pair before calling merge.

Changing the input lists

The code above creates a new list for each merged block. If you write current = ordered[0] instead of current = list(ordered[0]), then current refers to the same list as the caller's first interval. Then current[1] = ... changes the caller's data. The program below shows the effect.

The output is:

result: [[1, 6], [8, 10]]
data:   [[1, 6], [2, 6], [8, 10]]

The first interval in data was changed from [1, 3] to [1, 6], even though the function only returned a result. The copy with list(...) avoids this, and it is why the full program prints the input unchanged at the end.

A related point is the difference between sorted and the list method sort. The method sort changes the list it is called on and returns nothing. The function sorted returns a new list. The program below shows both.

The output is:

sorted() returns: [[1, 3], [2, 6], [8, 10]]
items after sorted(): [[8, 10], [1, 3], [2, 6]]
items after .sort():  [[1, 3], [2, 6], [8, 10]]

Use sorted when the caller needs the original order, and .sort() only when changing the list is intended.

Integer overflow does not happen in Python

In Java, an int holds numbers only up to about 2 billion, and subtracting two large numbers can wrap around to a wrong result. Python integers have no fixed size, so subtraction is always exact. The program below shows this.

The output is:

4000000000
1267650600228229401496703205376
<class 'int'>

Python still needs care with comparisons. The key lambda iv: iv[0] avoids any question about how to compare two intervals, because it compares only one number per interval.

Treating touching intervals as separate

The program merges [1, 2] and [2, 3] because the check is start <= current[1]. If the problem says that an end point is not part of the interval, for example half-open intervals such as [start, end) used for time ranges in some libraries, then the check should be start < current[1]. Read the problem statement before choosing between < and <=.

Practice

1. Merge the intervals [4, 5], [1, 2] and [2, 3]. Write the output.

Show the answer

[[1, 3], [4, 5]]. After sorting by start, the list is [1, 2], [2, 3], [4, 5]. The first two touch at 2, so they join into [1, 3]. The interval [4, 5] starts after 3, so it stands alone.

2. Busy times on a day from 0 to 24 are [1, 3], [2, 5] and [8, 9]. Find the free times, as a list of intervals.

Show the answer

[[0, 1], [5, 8], [9, 24]]. First merge the busy times into [1, 5] and [8, 9]. The free time is the gap before the first busy block, the gaps between blocks, and the gap after the last block. The gaps are 0 to 1, 5 to 8 and 9 to 24.

3. A person has these meetings: [0, 30], [5, 10] and [15, 20]. Can they attend all of them? Then check [7, 10] and [2, 4].

Show the answer

The first set gives False. After sorting, [5, 10] starts at 5, which is before [0, 30] ends at 30, so the meetings overlap. The second set gives True, because after sorting, [2, 4] ends at 4 and [7, 10] starts at 7, so there is no overlap. The check is to sort by start and look for any interval that starts before the previous one ends.

4. The intervals [1, 4], [2, 5] and [7, 9] are given. How many intervals disappear when the list is merged?

Show the answer

One interval disappears. The merged list is [1, 5] and [7, 9], which has 2 intervals, down from 3. The count removed is the input length minus the output length, which is len(intervals) - len(merged).

5. Give the output of the merge for [1, 4] and [0, 0].

Show the answer

[[0, 0], [1, 4]]. After sorting, [0, 0] comes first. Its end is 0, which is before the start of [1, 4], so they do not overlap and both stay in the output, in sorted order.

Summary

• Sort intervals by their start value with sorted before scanning, because overlaps can only happen between neighbours in a sorted list.
• Keep one current interval, extend its end with max, and save it when the next interval starts after its end.
• Do not forget to save the last interval after the loop.
• The sort costs about n log n steps and the scan costs about n steps, so the sort dominates.
• Copy a list with list(...) before changing it, so the caller's data stays the same.
• Check whether touching intervals should merge, since that depends on the problem.