Merging intervals

Why this matters

Many programs store ranges of numbers: a meeting from 9 to 10, a file that covers bytes 0 to 4095, a booking from day 3 to day 5. A list of these ranges often has overlaps. Two meetings may cover the same hour, or two bookings may share a day. A program that reports free time, or that checks which part of a calendar is busy, needs one clean list where no range overlaps another.

This lesson shows how to turn a messy list of ranges into a clean one. The method sorts the list once and then walks through it one time. It uses the sorting skills from the sorting lessons earlier in the course and the array and vector basics from the arrays lesson. The binary search lessons in this module look at a different question: finding one value fast in an ordered list.

What an interval is

An interval is a range from a start value to an end value. In this lesson, an interval [1, 3] covers every number from 1 to 3, including both ends. We call this a closed interval. Its start is 1 and its end is 3.

In C++, we store one interval with a small struct that has two integers:

struct Interval {
    int start;
    int end;
};

A list of intervals is a std::vector<Interval>. The list may come in any order. The input {{1, 3}, {2, 6}, {8, 10}, {15, 18}} has intervals that are already sorted by start, but many inputs are not.

Two intervals overlap when they share at least one number. The intervals [1, 3] and [2, 6] overlap, because the number 2 is in both. The intervals [1, 3] and [8, 10] do not overlap, because no number is in both.

Merging means replacing two overlapping intervals with one interval that covers both. [1, 3] and [2, 6] merge into [1, 6]. The result covers every number that either input covered.

The two-interval case

Start with two intervals, a and b. When do they overlap?

Look at where b starts. If b.start is larger than a.end, then b starts after a stops, and there is a gap between them. If b.start is less than or equal to a.end, then b starts while a is still running, so they overlap. In that case the merged interval starts at a.start and ends at the larger of the two ends.

Example: a = [1, 3] and b = [2, 6]. Here b.start is 2, which is less than or equal to a.end, which is 3. They overlap. The merged interval is [1, max(3, 6)], which is [1, 6].

Example: a = [1, 3] and b = [8, 10]. Here b.start is 8, which is larger than a.end, which is 3. There is a gap, so they do not merge.

This check is the core of the method. The rest of the lesson uses it on a whole list.

Why sorting comes first

The check above works when intervals come in order of their start. Suppose a list is out of order. The interval [8, 10] appears first, then [1, 3], then [2, 6]. If we compare each interval with the one before it, we compare [1, 3] with [8, 10], see a gap, and never connect [1, 3] with [2, 6].

Sorting by start puts the intervals in left to right order. Then each interval can only overlap the one most recently kept in the result, or start a new group. A sort costs about n log n steps for n intervals, and the merge pass after it costs n steps. The sort is the expensive part.

The program below shows the method on five inputs. The first is the standard example. The second has two intervals that touch at one number. The third has an interval that covers the next one. The fourth is out of order. The fifth is empty.

C++ · editable

#include <algorithm>
#include <iostream>
#include <vector>

struct Interval {
    int start;
    int end;
};

std::vector<Interval> merge_intervals(std::vector<Interval> intervals) {
    std::vector<Interval> merged;
    if (intervals.empty()) {
        return merged;
    }
    std::sort(intervals.begin(), intervals.end(),
              [](const Interval& a, const Interval& b) { return a.start < b.start; });
    merged.push_back(intervals[0]);
    for (std::size_t i = 1; i < intervals.size(); ++i) {
        Interval& last = merged.back();
        if (intervals[i].start <= last.end) {
            last.end = std::max(last.end, intervals[i].end);
        } else {
            merged.push_back(intervals[i]);
        }
    }
    return merged;
}

void print(const std::vector<Interval>& list) {
    std::cout << "[";
    for (std::size_t i = 0; i < list.size(); ++i) {
        std::cout << (i ? ", " : "") << "[" << list[i].start << ", " << list[i].end << "]";
    }
    std::cout << "]\n";
}

int main() {
    print(merge_intervals({{1, 3}, {2, 6}, {8, 10}, {15, 18}}));
    print(merge_intervals({{1, 4}, {4, 5}}));
    print(merge_intervals({{1, 10}, {2, 3}, {4, 5}}));
    print(merge_intervals({{5, 6}, {1, 2}, {2, 4}}));
    print(merge_intervals({}));
}

The output is:

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

The code works in four steps.

If the input is empty, return an empty list. Without this check, intervals[0] would read from an empty vector, which is undefined behaviour.
Sort a copy of the list by start. The sort uses a lambda, a small function written inline, to compare two intervals. The lambda returns true when a should come before b.
Put the first interval into merged. This interval is the first group.
For each later interval, look at the last group in merged. If the new interval starts at or before that group ends, extend the group. Otherwise, add the new interval as a new group.

Walking through the first example

Here is the first input after sorting, with the state of merged after each step.

Step	Interval read	Check	Result after this step
1	`[1, 3]`	first, nothing to compare	`[1, 3]`
2	`[2, 6]`	2 is at most 3, so overlap	`[1, 6]`
3	`[8, 10]`	8 is more than 6, so gap	`[1, 6]`, `[8, 10]`
4	`[15, 18]`	15 is more than 10, so gap	`[1, 6]`, `[8, 10]`, `[15, 18]`

The list is walked once. Each interval is read one time and either joins the last group or starts a new one.

The end must be the largest seen so far

The most common error in this method is setting the end of the group to the end of the new interval, instead of to the larger of the two ends. The second and third examples in the program show why.

The third example has [1, 10], then [2, 3], then [4, 5]. The interval [1, 10] covers everything. The later intervals sit inside it. If the code sets the end to the new interval's end, the group shrinks each time.

Here is that wrong version. The only change from the program above is the line last.end = intervals[i].end; in place of the std::max line. This small program prints the wrong result:

C++ · editable

Its output is:

[1, 3] [4, 5]

The correct answer is [1, 10]. The wrong version lost the end 10 when it read [2, 3], and then started a new group at [4, 5]. The fix is to keep the larger end: last.end = std::max(last.end, intervals[i].end);.

Touching intervals

Two intervals that share an end point, such as [1, 4] and [4, 5], overlap at the number 4. Because the intervals are closed, the number 4 belongs to both. The program merges them into [1, 5]. This is the rule used by the check intervals[i].start <= last.end. The <= sign is what makes touching intervals merge.

Some problems use a different rule. An interval written [1, 4) stops just before 4, so [1, 4) and [4, 5) do not overlap. For that rule, change <= to <. Read the problem statement before you choose.

Worked example: free time in a day

A common use of merged intervals is to find the gaps. Suppose a person has meetings, and we want the free times between 8 and 20. Merge the meetings first. The merged list is a clean list of busy blocks, sorted and with no overlaps. The free times are the gaps between those blocks, plus the time before the first block and after the last one.

The function free_time walks the merged blocks with a variable called cursor. The cursor is the first moment that is not yet known to be busy. For each busy block, if the block starts after the cursor, the time from the cursor to the block's start is free. Then the cursor moves to the end of the block. The std::max keeps the cursor from moving backward when a block is inside an earlier one. After the loop, any time from the cursor to the end of the day is free too.

The meetings in the program overlap in places, so the merge step matters. The meetings [9, 10] and [9, 11] become [9, 11], and [16, 18] and [17, 19] become [16, 19].

C++ · editable

#include <algorithm>
#include <iostream>
#include <vector>

struct Interval {
    int start;
    int end;
};

std::vector<Interval> free_time(const std::vector<Interval>& busy, int day_start, int day_end) {
    std::vector<Interval> gaps;
    int cursor = day_start;
    for (const Interval& b : merge_intervals(busy)) {
        if (b.start > cursor) {
            gaps.push_back({cursor, b.start});
        }
        cursor = std::max(cursor, b.end);
    }
    if (cursor < day_end) {
        gaps.push_back({cursor, day_end});
    }
    return gaps;
}

int main() {
    std::vector<Interval> busy = {{9, 10}, {9, 11}, {13, 14}, {16, 18}, {17, 19}};
    std::cout << "busy, merged: ";
    print(merge_intervals(busy));
    std::cout << "free between 8 and 20: ";
    print(free_time(busy, 8, 20));
    std::cout << "free between 9 and 11: ";
    print(free_time({{9, 10}}, 9, 11));
    std::cout << "free with no meetings: ";
    print(free_time({}, 8, 12));
}

The output is:

busy, merged: [[9, 11], [13, 14], [16, 19]]
free between 8 and 20: [[8, 9], [11, 13], [14, 16], [19, 20]]
free between 9 and 11: [[10, 11]]
free with no meetings: [[8, 12]]

Read the first free time by hand. The day starts at 8, and the first busy block starts at 9. So [8, 9] is free. The cursor then moves to 11. The next block starts at 13, so [11, 13] is free. The last free time, [19, 20], comes from the code after the loop, because the cursor stops at 19 and the day ends at 20.

The third case shows the edge at the end of the day. The busy block covers the start of the day, so the only free time is [10, 11]. The fourth case has no meetings, so the whole day is one free block. An empty input is handled by merge_intervals, which returns an empty list, and the loop does nothing.

Common mistakes

Forgetting to sort. Without a sort, the check compares each interval only with the last group, not with the group it should join. The program below has the same merge loop, but it does not sort the input. It prints one interval for an input that should give two:

C++ · editable

Its output is:

[8, 10]

The correct answer is [1, 6] [8, 10]. The interval [1, 3] is read after [8, 10], so the check 1 <= 10 merges it into the group that starts at 8. The group keeps the start 8, so the start 1 is lost. The interval [2, 6] is absorbed the same way.

Sorting by the end instead of the start. The merge walk needs intervals in order of start. Sorting by end gives a different order, and the check then compares the wrong pairs. On the input {{1, 10}, {2, 3}, {4, 5}}, sorting by end and running the same walk gave [2, 3] [4, 10]. That is wrong, because the answer is [1, 10].

Misspelling a field name. The struct has start and end in lower case. Writing End gives a compile error. The following message came from g++ 15.2.0 for a line that wrote v[0].End in place of v[0].end:

wrong.cpp: In function ‘int main()’:
wrong.cpp:30:23: error: ‘__gnu_cxx::__alloc_traits<std::allocator<Interval>, Interval>::value_type’ {aka ‘struct Interval’} has no member named ‘End’; did you mean ‘end’?
   30 |     std::cout << v[0].End << "\n";
      |                       ^~~
      |                       end

The message names the struct and suggests end. Fix the name and the error goes away.

Skipping the empty-list check. Reading intervals[0] on an empty vector is undefined behaviour. The check at the top of merge_intervals avoids this. If you remove it, the empty input may crash or print garbage.

Practice

Exercise 1. Merge {{1, 2}, {3, 4}, {5, 6}}.

Show the answer

No two intervals overlap. The number 2 is not in [3, 4], and 4 is not in [5, 6]. The output is [[1, 2], [3, 4], [5, 6]], the same as the input. The program above printed that result.

Exercise 2. Merge {{1, 4}, {0, 4}}.

Show the answer

After sorting by start, the list is [0, 4] then [1, 4]. The second interval starts at 1, which is at most 4, so it merges. The end stays 4 because it is the larger end. The output is [[0, 4]].

Exercise 3. Merge {{1, 2}, {1, 5}}. Then explain why sorting by start alone is enough here.

Show the answer

Both intervals start at 1. The sort puts them next to each other in either order. The second interval starts at 1, which is at most the end 2, so it merges. The end is the larger of 2 and 5, which is 5. The output is [[1, 5]]. Sorting by start alone is enough here, because the walk only needs the intervals in order of start. The largest end is kept separately, in last.end.

Exercise 4. Merge {{2, 3}, {4, 5}, {6, 7}, {8, 9}, {1, 10}}.

Show the answer

After sorting, the list is [1, 10], [2, 3], [4, 5], [6, 7], [8, 9]. The first interval covers all the others, and each later start is at most 10. So every interval merges into the group. The output is [[1, 10]].

Exercise 5. A list has one million intervals. Roughly how many steps does the sort take, and how many steps does the merge walk take?

Show the answer

The sort takes about n log2 n steps. Since log2 of one million is about 20, the sort takes about 20 million steps. The merge walk reads each interval once, so it takes about one million steps. The sort is the bigger cost, and it decides the total.

Summary

An interval is a closed range from start to end, and two intervals overlap when the later one starts at or before the earlier one ends.
Sort the intervals by start first, so that each interval can only join the most recent group or start a new one.
In one walk, extend the last group when the new interval overlaps it, and keep the larger of the two ends.
Check for an empty list before reading the first interval.
The method costs about n log n for the sort and n for the walk.

Merging intervals

Why this matters

What an interval is

The two-interval case

Why sorting comes first

Walking through the first example

The end must be the largest seen so far

Touching intervals

Worked example: free time in a day

Common mistakes

Practice

Summary

Stuck? Ask the tutor