Merge Intervals Explained: Sorting and Overlap Rules

By Hourly DSA · September 29, 2026 · 4 min read

To merge overlapping intervals, sort them by start position, then scan while extending the current merged interval. When the next interval starts beyond the current end, save the current interval and begin a new one.

The main decisions are what counts as overlap and how to update the end. Make both precise before writing the loop.

Start with the interval convention

For this example, intervals are closed: [2, 5] includes both 2 and 5. Two intervals that share an endpoint therefore overlap. We assume each interval has a start no greater than its end.

Consider:

[7, 9], [1, 4], [3, 6], [10, 12]

Sorting by start gives:

[1, 4], [3, 6], [7, 9], [10, 12]

Keep [1, 4] as the current interval. The next start, 3, is at most the current end, 4, so merge them into [1, 6].

The next start is 7, which is greater than 6. Save [1, 6] and start [7, 9]. The final interval starts at 10, so it also stays separate.

The result is [1, 6], [7, 9], [10, 12].

Why sorting makes one scan enough

After sorting, every future start is at least as large as the start you are examining now.

If the next start is already greater than the current end, no later interval can bridge that gap. Its start will be just as large or larger. You can safely finalize the current merged interval.

Without sorting, a later interval might begin earlier and overlap a range you already saved. Comparing only neighboring intervals in the original input would miss that connection.

This is the reason for the sort, not just a preparation step to memorize.

Nested intervals need the maximum end

Now merge:

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

All three belong to [1, 10]. When [2, 3] overlaps the current interval, its end must not shrink the current end from 10 to 3.

Update with:

current.end = max(current.end, next.end)

Using current.end = next.end would lose covered positions. It could also make [4, 8] appear separate even though the original [1, 10] contains it.

Try a contained interval when reviewing a merge solution. Testing only ranges that steadily extend to the right will not expose this bug.

The complete scan in pseudocode

For empty input, return an empty result. Otherwise, sort the intervals, copy the first interval into current, and run:

for next in the remaining intervals:
    if next.start <= current.end:
        current.end = max(current.end, next.end)
    else:
        append current to result
        current = a copy of next
append current to result

The final append matters. The loop saves an interval only when it sees a gap. The last current interval has no later gap to trigger that action.

Copying also makes mutation intent explicit. If you reuse and modify the input's interval objects, callers may observe those changes.

Do touching intervals merge?

Under the closed-interval rule above, [1, 3] and [3, 5] overlap at 3 and merge into [1, 5].

Meeting schedules often use half-open intervals: [1, 3) ends just before 3, and [3, 5) begins at 3. Those meetings do not overlap, so a conflict check uses a strict comparison between the next start and current end.

A task that asks you to combine continuous coverage may still allow adjacent half-open ranges to merge. The desired output determines whether touching is enough. State that policy instead of assuming every interval problem uses the same inequality.

If the task is to select as many compatible meetings as possible, the objective changes again. That calls for greedy interval scheduling, not merging all covered time.

What are the complexity bounds?

Sorting n intervals with a comparison sort takes O(n log n) time. The scan takes O(n), so sorting dominates. Already sorted input only needs the linear scan.

The result can contain n intervals, requiring O(n) output space. Beyond the result, the scan uses one current interval and a few variables. Sorting may require additional memory depending on the implementation, and preserving the input may require a copy.

Explain those costs separately rather than declaring the whole solution constant-space because the loop uses few variables.

A short practice check

Using closed intervals, what does [2, 8], [3, 4], [8, 11] become?

[2, 11]. The middle interval is contained, and the final interval overlaps at 8. Both the maximum-end rule and the endpoint convention matter.

Use Hourly DSA for focused reasoning practice. When a trace goes wrong, the DSA mistake-review guide shows how to turn a case like this into a short question you can revisit.