Introduction

Merging ranges means combining intervals that overlap, and sometimes intervals that touch, into a smaller set of non-overlapping results. It is a standard algorithm problem because the right solution is simple once the data is sorted, but easy to get subtly wrong if edge cases are ignored.

The Core Idea

Suppose you start with these intervals:

[1, 3], [2, 6], [8, 10], [9, 12]

The merged result is:

[1, 6], [8, 12]

The usual algorithm is:

1. sort by start value
2. walk from left to right
3. merge into the current interval when overlap exists
4. otherwise start a new interval

Without sorting, you cannot reliably know whether the next interval should merge with the current one.

A Clean C++ Implementation

Here is a practical C++ version using a small struct and std::vector:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5struct Range {
6    int start;
7    int end;
8};
9
10std::vector<Range> mergeRanges(std::vector<Range> ranges) {
11    if (ranges.empty()) {
12        return {};
13    }
14
15    std::sort(ranges.begin(), ranges.end(),
16              [](const Range& a, const Range& b) {
17                  return a.start < b.start;
18              });
19
20    std::vector<Range> merged;
21    merged.push_back(ranges[0]);
22
23    for (size_t i = 1; i < ranges.size(); ++i) {
24        Range& last = merged.back();
25        const Range& current = ranges[i];
26
27        if (current.start <= last.end) {
28            last.end = std::max(last.end, current.end);
29        } else {
30            merged.push_back(current);
31        }
32    }
33
34    return merged;
35}
36
37int main() {
38    std::vector<Range> ranges = {
39        {1, 3}, {2, 6}, {8, 10}, {9, 12}
40    };
41
42    for (const auto& range : mergeRanges(ranges)) {
43        std::cout << "[" << range.start << ", " << range.end << "]\n";
44    }
45}

This code sorts a copy of the input, merges in one pass, and returns the result. The logic is easy to test because each interval is handled exactly once after sorting.

Decide Whether Touching Ranges Should Merge

One subtle design choice is whether adjacent ranges count as mergeable.

For example:

[1, 3] and [4, 5]

Do these stay separate, or should they become [1, 5] because they touch conceptually in your domain

The answer depends on the rules of the problem. The earlier condition:

if (current.start <= last.end)

merges only true overlap. If you want to merge touching integer ranges too, you might use:

if (current.start <= last.end + 1)

That one-character change affects the meaning of the whole algorithm, so it should be deliberate.

Complexity

The time cost is dominated by sorting:

• sorting takes O(n log n)
• the merge scan takes O(n)

So the total time is O(n log n), and the extra output storage is O(n) in the worst case if nothing merges.

That is already optimal for an unsorted input list in ordinary comparison-based code.

Why Sorting First Is Better Than Pairwise Checking

Beginners sometimes try every interval against every other interval. That approach becomes messy and inefficient because merging one pair can create new overlap with a third interval, which then forces another pass.

Sorting avoids that problem. Once intervals are ordered by start value, you only need to compare the current interval with the last merged result.

That is why this problem is really more about ordering than about clever nested conditionals.

Common Pitfalls

• Forgetting to sort first, which makes the one-pass merge logic unreliable.
• Using the wrong overlap rule for the domain, especially when touching ranges may or may not count as merged.
• Failing to update the merged end with std::max, which can shrink a range incorrectly.
• Not handling empty input before reading ranges[0].
• Mutating the caller's original vector unexpectedly when the function should operate on a copy.

Summary

• Merging ranges is usually solved by sorting intervals and then scanning once from left to right.
• After sorting, each new range either extends the current merged interval or starts a new one.
• The overlap condition defines the business rule, especially for touching ranges.
• The standard solution runs in O(n log n) time because sorting dominates.
• Most bugs come from skipped sorting, wrong overlap logic, or weak edge-case handling.