Merge intervals and insert an interval in Python

Why this matters

A calendar app has a list of busy times. Two meetings that overlap should show as one busy block. A video editor has a list of clips on a timeline. Clips that overlap should be grouped. A booking system stores free slots, and when a new booking comes in, the free slots need to be updated.

All of these need the same skill. You have a list of ranges, which are called intervals, and you need to combine them, split them, or add to them while keeping the list clean.

This lesson covers two problems that use the same idea.

• Merge intervals. Given a list of intervals, combine every group that overlaps into one interval.
• Insert an interval. Given a sorted list of intervals that do not overlap, add one new interval and keep the result sorted and free of overlaps.

The sweep idea used here is a greedy approach. After sorting, each step makes a fixed choice that is never changed. The balloon lesson, Balloons: minimum arrows, used sorting by end. This lesson sorts by start.

Intervals and overlap, in plain words

An interval is a range from a start number to an end number, where both ends are included. We write [1, 3] for the numbers from 1 to 3, including 1 and 3. In Python, we store an interval as a small class made with @dataclass. A dataclass is a short way to write a class that holds named fields. You get Interval(1, 3) with fields start and end.

Two intervals overlap if they share at least one number. [1, 3] and [2, 6] overlap, because both contain 2 and 3. [1, 3] and [4, 6] do not overlap, because no number is in both. The pair [1, 4] and [4, 5] do overlap, because both contain 4. They touch at one point, and that point counts.

Merging two overlapping intervals gives one interval. It starts at the smaller start and ends at the larger end. So [1, 3] and [2, 6] merge into [1, 6].

Start with a small list

Take this list of four intervals:

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

Look at the first two. They overlap, so they merge into [1, 6]. The third interval starts at 8, which is after 6, so it does not touch the first group. The fourth starts at 15, which is after 10. So the answer is:

[1, 6]
[8, 10]
[15, 18]

Doing this by eye is easy for four intervals. For a list of thousands, you need a method that does not compare every pair. The method is to sort the intervals by start, and then walk through them once.

The idea: sort by start, then sweep

Sort the list so the intervals are in order of their start numbers. Then walk through the list from left to right, and keep one current group, which is the merged interval you are building right now.

For each interval in the sorted list:

1. If there is no current group yet, start one with this interval.
2. If this interval starts at or before the current group ends, it overlaps the group. Extend the group's end to the larger of the two ends.
3. Otherwise, this interval starts after the group ends. Close the group, save it, and start a new group with this interval.

At the end, save the last group.

Why does this work? After sorting, every later interval starts at or after the current one. So if the next interval starts after the group ends, no interval after it can reach back and overlap the group. The group is finished. This is the reason the walk only ever looks at the last group in the result.

Why the end must be the larger of two ends

A common mistake is to set the group's end to the new interval's end, without checking which end is larger. Take this list:

[1, 10]
[2, 3]
[4, 5]

The first interval covers the whole range from 1 to 10. The second and third sit inside it.

• The group starts as [1, 10].
• [2, 3] starts at 2, which is at or before 10, so it overlaps. The end should stay 10, not move down to 3. The larger of 10 and 3 is 10.
• [4, 5] also sits inside the group. Again the end stays 10.

The merged result is [1, 10]. If you set the end to the new interval's end each time, the group would become [1, 3] and then [1, 5], which loses the part from 5 to 10.

Worked example 1: merge the four intervals

Here is the full program for merging. It uses a list of dataclass objects.

The output is:

[Interval(start=1, end=6), Interval(start=8, end=10), Interval(start=15, end=18)]

Points to notice in the code.

• @dataclass(frozen=True) writes the class for you. The frozen=True part means the fields cannot change after the object is made. This is like a Java record. Because of this, the code cannot change last.end in place. It makes a new Interval instead.
• sorted(intervals, key=lambda item: item.start) returns a new list in order of start. The key tells sorted what to compare. A lambda is a short function with no name. lambda item: item.start means "for each item, take its start". The caller's list is not changed.
• merged is the result list. merged[-1] is its last item. A negative index counts from the end, so -1 is the last item and -2 is the one before it.
• if merged and ... is the empty-list check. An empty list counts as false in an if, so for the first interval the test stops early and the else branch adds it.
• max returns the larger of two numbers. Python has it built in, so no import is needed.

Worked example 2: a chain of touching intervals

Some intervals form a chain, where each one touches the next. Take [1, 2], [2, 3] and [3, 4]. Each pair shares an end point, so each pair overlaps.

• The group starts as [1, 2].
• [2, 3] starts at 2, which is at or before 2, so it joins the group. The end becomes 3.
• [3, 4] starts at 3, which is at or before 3, so it joins. The end becomes 4.

The result is [1, 4], one interval. Using <= in the check is what makes touching intervals merge. If the check used <, the chain would split into three pieces.

Why the sort must come first

The sweep only works on sorted input. Take three intervals in a jumbled order: [8, 10], [1, 3], [2, 6]. Run the sweep without sorting.

• The group starts as [8, 10].
• [1, 3] starts at 1. Is 1 at or before 10? Yes. So the code treats it as overlapping, and the group becomes start 8, end 10. The start stays at 8, even though 1 is smaller.
• [2, 6] also starts before 10, so it is absorbed too.

The output is one interval, [8, 10], which loses the range from 1 to 6 entirely. Sorting first puts [1, 3] and [2, 6] ahead of [8, 10], so the sweep builds the groups in the right order.

The sweep also handles the less tidy case where the input is not in order. A six-interval example shows this:

six = [Interval(9, 12), Interval(1, 2), Interval(5, 7), Interval(2, 4), Interval(6, 8), Interval(12, 13)]
print(merge(six))

Sorted by start, the list is [1, 2], [2, 4], [5, 7], [6, 8], [9, 12], [12, 13]. The sweep makes three groups: [1, 2] and [2, 4] join into [1, 4], then [5, 7] and [6, 8] join into [5, 8], then [9, 12] and [12, 13] join into [9, 13]. The output is:

[Interval(start=1, end=4), Interval(start=5, end=8), Interval(start=9, end=13)]

Each group is built from the intervals that touch it, in the order they appear after the sort. The method never needs to go back to an earlier group.

Python's sorted leaves the original list alone. The list method sort changes the list it is called on, and it returns None. The next example shows this:

The output is:

sort returns: None
items now: [Interval(start=1, end=3), Interval(start=2, end=6), Interval(start=8, end=10)]

Use sorted(...) when the caller needs the original order. Use list.sort() when you own the list and do not need the old order.

Insert one interval into a sorted list

The second problem starts from a list that is already sorted by start and has no overlaps. You add one new interval. The result must still be sorted and have no overlaps.

You could add the new interval to the end, sort the whole list, and call merge. That works, but it sorts the whole list again. There is a faster way that does one pass.

The list falls into three parts, and the new interval can only touch the middle one.

1. Before. Intervals that end before the new interval starts. They do not touch it. Keep them as they are.
2. Overlap. Intervals that overlap the new interval. Combine them with the new interval into one interval. The new start is the smallest start, and the new end is the largest end.
3. After. Intervals that start after the new interval ends. Keep them as they are.

Because the list is sorted, the three parts appear in that order, and each is one unbroken run. So three steps, one after another, do the job.

Worked example 3: insert into the middle

Start with the list [1, 3], [6, 9]. Insert [2, 5].

• Before. [1, 3] ends at 3. Is 3 less than 2? No. So [1, 3] is not before the new interval. It overlaps. The before part is empty.
• Overlap. The group starts as [2, 5]. [1, 3] starts at 1, which is at or before 5, so it overlaps. The group becomes start 1, end 5. [6, 9] starts at 6, which is after 5, so the overlap part stops.
• After. [6, 9] is kept.

The result is [1, 5], [6, 9].

Now insert [4, 5] into the same list. The before check: [1, 3] ends at 3, which is less than 4, so it is kept as is. The overlap part starts with [4, 5]. The next interval, [6, 9], starts at 6, which is after 5, so nothing else joins. The result is [1, 3], [4, 5], [6, 9]. The new interval did not touch [1, 3], so the two stay apart.

Here is the Python code for the three parts. It is a full program:

Its output is:

[Interval(start=1, end=5), Interval(start=6, end=9)]
[Interval(start=1, end=3), Interval(start=4, end=5), Interval(start=6, end=9)]
[Interval(start=0, end=0), Interval(start=1, end=3), Interval(start=6, end=9)]
[Interval(start=1, end=3), Interval(start=6, end=9), Interval(start=10, end=12)]
[Interval(start=5, end=7)]

The first while loop is the before part. The second is the overlap part. It uses min and max because the new group can grow on both sides. The last step, result.extend(intervals[i:]), is the after part. The expression intervals[i:] is a slice. A slice is a new list made from a range of positions. Here it takes everything from position i to the end. The variable i is a position in the input list, and it only moves forward, so the whole function takes one pass.

Each line matches the three parts. The [0, 0] case overlaps nothing, so it is added alone in the middle step, and the two intervals after it are kept. The [10, 12] case is the same, with the intervals before it kept first. The empty list is handled, because the loops do not run and the new interval is added on its own.

Worked example 4: one insert that joins several intervals

Take this list:

[1, 2]
[3, 5]
[6, 7]
[8, 10]
[12, 16]

Insert [4, 8].

• Before. [1, 2] ends at 2, which is less than 4. Keep it.
• Overlap. The group starts as [4, 8]. [3, 5] starts at 3, which is at or before 8. The group becomes start 3, end 8. [6, 7] starts at 6, which is at or before 8. It joins, end stays 8. [8, 10] starts at 8, which is at or before 8. It joins, and the end becomes 10. [12, 16] starts at 12, which is after 10. The overlap part stops.
• After. [12, 16] is kept.

The result is [1, 2], [3, 10], [12, 16]. Four intervals became one. Here is the output from running the code on this input:

[Interval(start=1, end=2), Interval(start=3, end=10), Interval(start=12, end=16)]

The case can also go the other way. Insert [0, 20] into the same five intervals. The new interval covers every one of them, so the before and after parts are empty, and the overlap loop absorbs all five. The output is:

[Interval(start=0, end=20)]

The function has no special case for this. The before and after parts simply keep nothing.

Common mistakes

Not taking the larger end. The example with [1, 10], [2, 3], [4, 5] shows the cost. A version of merge that sets the group's end to the new interval's end gives the wrong answer. Its key line is merged[-1] = Interval(last.start, nxt.end).

On that input it prints:

[Interval(start=1, end=3), Interval(start=4, end=5)]

The correct output is [Interval(start=1, end=10)]. The fix is max(last.end, nxt.end).

Using < instead of <=. Touching intervals must merge. With [1, 4] and [4, 5], the check nxt.start < merged[-1].end is false, since 4 is not less than 4. So the two stay separate, and the list has two intervals where one is right. A check that used < on the same two intervals would count 2 groups, while the correct count is 1. The check is nxt.start <= merged[-1].end.

Forgetting the empty-list check in merge. The first interval has no group before it, so merged is empty. If the code reads merged[-1] on an empty list, Python raises an error. Here is a small program that shows the message:

merged = []
last = merged[-1]

The output is:

Traceback (most recent call last):
  File "<your file path>", line 2, in <module>
    last = merged[-1]
           ~~~~~~^^^^
IndexError: list index out of range

The last line is the one to read first. It names the error type, IndexError, and says the position was not in the list. The lines above it show the file and line number on your machine, so your path will differ. The if merged and ... check stops the code from reaching that line for the first interval.

Changing a frozen interval. Because Interval is frozen, a line like last.end = 10 fails. Here is the error:

from dataclasses import dataclass
 
 
@dataclass(frozen=True)
class Interval:
    start: int
    end: int
 
 
iv = Interval(1, 2)
iv.end = 5

The output is:

Traceback (most recent call last):
  File "<your file path>", line 11, in <module>
    iv.end = 5
    ^^^^^^
  File "<string>", line 16, in __setattr__
dataclasses.FrozenInstanceError: cannot assign to field 'end'

The line numbers in the middle of this error depend on your Python version. The fix is to make a new object, such as Interval(iv.start, 5). This is the same reason merge replaces the last item instead of changing it.

Assuming the input is sorted in insert. The insert function is only correct when the input list is sorted by start and has no overlaps. If the list is not sorted, the three-part walk gives a wrong answer and may not give a sorted result. Sort the list first, or use merge on the full list when you cannot trust the input.

Sorting by end in merge. Sorting by end works for the balloon problem, but here it breaks the rule that every later interval starts at or after the current one. Use key=lambda item: item.start.

Practice

Exercise 1

Merge [1, 2], [2, 3], [3, 4] into the smallest list of intervals.

Show the answer

The result is [1, 4]. Each interval touches the next at one point, and the check <= joins touching intervals. So the three form one group that runs from 1 to 4.

Exercise 2

Merge [1, 4] and [0, 0]. Show the output in the same form as the merge output above.

Show the answer

Sorted by start, the list is [0, 0], [1, 4]. The point 0 does not reach 1, so the two stay apart. The output is [Interval(start=0, end=0), Interval(start=1, end=4)].

Exercise 3

Insert [5, 6] into the list [1, 2], [3, 5], [6, 7], [8, 10], [12, 16]. Give the result.

Show the answer

Before: [1, 2] ends at 2, which is less than 5, so it is kept. Overlap: the group starts as [5, 6]. [3, 5] starts at 3, which is at or before 6, so the group becomes start 3, end 6. [6, 7] starts at 6, which is at or before 6, so the end becomes 7. [8, 10] starts at 8, which is after 7, so the overlap part stops. After: [8, 10] and [12, 16] are kept. Result: [1, 2], [3, 7], [8, 10], [12, 16].

Exercise 4

Write a function count_groups(intervals) that returns how many separate groups remain after merging. It must not build the merged list.

Show the answer

The output is 3 and then 0. The function keeps only the end of the current group, not the whole group. For the first example, the groups are [1, 6], [8, 10] and [15, 18], so the function returns 3. The ordered[1:] slice skips the first item, which has already been used to start the first group.

Exercise 5

Explain in two or three sentences why the insert function never needs to look at an interval in the "before" part after the overlap part has started.

Show the answer

The list is sorted by start and no two intervals overlap, so each interval ends before the next one starts, and the ends rise along the list. The before loop stops at the first interval whose end is not less than the new start. Every interval after that one ends even later, so none of them can be in the before part.