Merge Intervals: Sort and Sweep

LeetCode 56, Merge Intervals, is one of those problems that comes up everywhere. Calendar apps, scheduling systems, genomic range queries, even compilers use interval merging internally. It is also the gateway to an entire family of interval problems on LeetCode. Once you can merge overlapping intervals cleanly, problems like Insert Interval, Meeting Rooms, and Non-overlapping Intervals become much more approachable.

Let's break it down.

The problem

You are given an array of intervals where each interval is a pair [start, end]. Merge all overlapping intervals and return a list of non-overlapping intervals that cover all the ranges in the input.

Two intervals overlap when one starts before or at the point where the other ends. For example, [1,3] and [2,6] overlap because 2 falls inside [1,3]. Their merge is [1,6].

Here is the classic example:

The input has four intervals. Two of them overlap ([1,3] and [2,6]), so they get merged into [1,6]. The other two do not overlap with anything, so they pass through unchanged.

Why sorting is the key

If the intervals are in random order, you would need to compare every pair to find overlaps. That is O(n^2). But if you sort the intervals by their start value, something nice happens: overlapping intervals are always adjacent (or close to adjacent) in the sorted order. You only need to look at the interval right before the current one to decide whether they overlap.

Sorting reduces the problem from "find all overlapping pairs" to "scan left to right and merge neighbors." That is the core insight.

The algorithm: sort and sweep

1. Sort the intervals by start time.
2. Initialize a result list with the first interval.
3. Sweep through the remaining intervals. For each one:
   • If the current interval overlaps with the last interval in the result (current start is at or before last end), extend the last interval's end to max(last end, current end).
   • Otherwise, add the current interval to the result as a new entry.

That is it. Sort, then one linear pass.

def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]

    for start, end in intervals[1:]:
        last = merged[-1]

        if start <= last[1]:
            # Overlapping: extend the end
            last[1] = max(last[1], end)
        else:
            # No overlap: start a new interval
            merged.append([start, end])

    return merged

Short and clean. The <= in the overlap check handles the edge case where intervals touch at a single point (like [1,3] and [3,5]), which the problem considers overlapping.

Visual walkthrough

Let's trace through the algorithm on [[1,3],[2,6],[8,10],[15,18]]. After sorting (these are already sorted), we process each interval one at a time.

The key moment is step 2. When we process [2,6], we see that 2 is less than or equal to 3 (the end of the last merged interval). That means overlap. We extend the end from 3 to 6, producing [1,6]. For the remaining intervals, their start values are well past the end of the last merged interval, so they get added as-is.

The overlap check, explained

The overlap condition start <= last[1] works because the intervals are sorted by start time. After sorting, we know:

• Every interval's start is greater than or equal to the previous interval's start.
• So the only question is: does the current interval start before the previous one ends?

If yes, they overlap. The merged interval keeps the earlier start (which is already last[0] since we sorted) and takes the later end (max(last[1], end)).

The max is important. Consider [1,10] and [2,5]. The second interval is completely contained within the first. Without max, you would shrink the merged interval from [1,10] to [1,5], which is wrong.

Edge cases

Single interval. If the input has only one interval, return it as-is. The code handles this naturally since the loop never executes.

Already non-overlapping. If no intervals overlap, the output is the same as the sorted input. Each interval gets appended without merging.

All intervals overlap. Something like [[1,4],[2,5],[3,6]] collapses into a single interval [[1,6]]. The sweep keeps extending the last interval's end.

Contained intervals. [[1,10],[2,3],[4,5]] becomes [[1,10]]. The smaller intervals are completely inside the first one, so max(10, 3) and max(10, 5) both keep the end at 10.

Complexity analysis

Time: O(n log n). Sorting takes O(n log n). The sweep is O(n). The sort dominates.

Space: O(n). The output list can contain up to n intervals (when none overlap). Some implementations sort in-place, but the output still requires O(n) space. Python's sort() uses O(n) auxiliary space internally (Timsort), so the total is O(n) either way.

You cannot do better than O(n log n) for this problem in the comparison-based model. You need to identify which intervals are neighbors, and that requires sorting (or equivalent work).

The building blocks

Merge Intervals is built from two fundamental bricks that show up across many LeetCode problems.

Sort-first reduction

Many problems become dramatically simpler once the input is sorted. The pattern is: sort the data to create an invariant (in this case, "intervals are ordered by start time"), then exploit that invariant in a linear scan. Without the sort, you are stuck with pairwise comparisons.

This same strategy powers:

• 3Sum (sort, then use two pointers on the remaining elements)
• Meeting Rooms II (sort events by time, then sweep with a heap)
• Non-overlapping Intervals (sort by end time, then greedy select)
• Largest Number (custom sort comparator on string representations)

If your brute force is O(n^2) and involves comparing pairs, ask yourself: would sorting give me a useful ordering to scan through?

Greedy merge with running state

As you sweep through sorted data, you maintain a "current" state (here, the last interval in the result) and decide whether to extend it or start fresh. The decision is local: you only look at the current element and the running state. No backtracking, no recursion.

This shows up in:

• Insert Interval (same merge logic, but you also need to find the insertion point)
• Non-overlapping Intervals (track the running end and count removals)
• Partition Labels (track the farthest reach of each character)

The key property that makes greedy work here is that sorting eliminates the need to look backward. Once you have processed an interval and moved on, you never revisit it.

Common variations

Once you have merge intervals down, these related problems are natural next steps:

Insert Interval (LeetCode 57). You are given a sorted, non-overlapping list and need to insert a new interval, merging as needed. The core merge logic is the same, but you also need to find where the new interval belongs.

Meeting Rooms II (LeetCode 253). Instead of merging, you count the maximum number of overlapping intervals at any point. The sort-first strategy is the same, but instead of merging you use a min-heap to track active meetings.

Non-overlapping Intervals (LeetCode 435). Find the minimum number of intervals to remove so the rest do not overlap. Sort by end time, then greedily keep intervals that do not conflict.

All three problems start with sorting. The interval merging building block carries over directly.

Reading about it is not enough

You have seen the sort-and-sweep pattern. You understand why sorting by start time creates the invariant that makes a linear scan work. But can you reproduce this solution from scratch in two weeks?

Merge Intervals is a problem where the code is short but the reasoning has several moving parts. Why sort by start, not end? Why <= instead of <? Why max(last[1], end) instead of just end? Each of those details is a potential bug if you have not internalized the logic.

The interval merging building block is compact enough to drill in isolation. Once it clicks, problems like Insert Interval and Meeting Rooms become variations on a theme rather than new problems to memorize from scratch.

Related posts

• Merge Sorted Array - Another merge problem, but with two sorted arrays instead of intervals
• 3Sum - Uses the same sort-first reduction to tame an O(n^3) brute force
• Contains Duplicate - Sorting as a strategy for detecting relationships between elements

---

Visual Learner? Understand the merge operation visually with our Merge Sort Interactive Visualization.