Algorithm

Merge Intervals

Greedy & Intervals Pattern

Merge Intervals

You are given an array of intervals where each interval is [start, end] with start ≤ end. Some intervals overlap or touch. Return a new array of non-overlapping intervals that cover exactly the same set of points, with every group of overlapping or touching intervals fused into one. Two intervals that share even a single endpoint (one ends where the next begins) are treated as connected and must be merged.

CONSTRAINTS
  • 1 ≤ intervals.length ≤ 10⁴
  • intervals[i].length == 2
  • 0 ≤ start ≤ end ≤ 10⁴
  • Intervals touching at an endpoint count as overlapping and are merged
EXAMPLE 1
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
The ranges [1,3] and [2,6] share the points from 2 to 3, so they fuse into [1,6]. The other two touch nothing and pass through unchanged.
EXAMPLE 2
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
The first ends exactly where the second begins. Because touching endpoints count as connected, they merge into a single [1,5].
EXAMPLE 3
Input: intervals = [[1,4],[2,3]]
Output: [[1,4]]
The second range lies entirely inside the first, so the merged end must stay 4 rather than shrinking to 3 — this is why the end is updated with a maximum.
EXAMPLE 4
Input: intervals = [[1,4],[5,6]]
Output: [[1,4],[5,6]]
There is a gap between 4 and 5, so the ranges are disjoint and both survive separately.
EXAMPLE 5
Input: intervals = [[5,5]]
Output: [[5,5]]
A single point is a valid interval on its own and, with nothing to merge into, is returned as-is.
Do intervals that only touch, like [1,4] and [4,5], count as overlapping?
In this problem, yes — they merge into [1,5]. This is a convention worth confirming, since a stricter definition where touching does not count would change the comparison from start ≤ end to start < end and produce different output.
Is the input sorted?
No, it may arrive in any order, so you must sort it yourself. Sorting by start time is what makes overlaps local and the single sweep possible.
Should the output be sorted?
Yes, the merged intervals come out sorted by start as a natural consequence of sorting the input first, which is the expected form of the answer.
Can an interval be a single point where start equals end?
Yes. A point like [5,5] is valid and merges normally if it touches or falls inside another interval.
What makes this hard is the ordering

You are handed a bag of time ranges, thrown in with no order, and asked to fuse every cluster of overlapping or touching ranges into single ranges. The output covers the exact same points, just written with the fewest intervals.

The difficulty is entirely that the input is unordered. Two intervals that belong to the same merged clump could sit at opposite ends of the array. If you try to merge in place, one merge can create a new overlap with something you already passed, and you find yourself looping over the list again and again.

The naive approach, and the cost of disorder

Compare every interval against every other; when two overlap, fuse them and start over, because the fusion might now reach something else.

python
# Repeatedly scan all pairs, merging any overlap, until a full
# pass finds nothing to merge. O(N²) per pass, several passes.

This is slow and fiddly precisely because overlaps can chain in any direction. The fix is to impose order first.

The reframe: sort by start, and overlaps become local

Sort the intervals by start time. This buys one powerful guarantee: if two intervals overlap, the earlier-starting one comes first, so any interval that could touch the current one is immediately adjacent in the sorted order. You never have to look backward past the interval you just finished, and you never have to look forward past the next one. A tangled all-pairs problem becomes a single left-to-right sweep.

Why does sorting by start give this? After sorting, each interval's start is at least the previous start. So when you hold a running "current merged block", the only way a later interval can overlap it is by starting at or before the block's current end. Anything starting after the block's end starts a fresh block — and because starts only increase, nothing later can reach back into the old block either.

The sweep

Keep the last block in your result list as an anchor. For each next interval, decide: does it reach the anchor, or start a new block?

- It overlaps or touches if its start is ≤ the anchor's end. Extend the anchor's end to the larger of the two ends. (Take the max, not simply the new end — the next interval might be entirely swallowed inside the anchor, in which case the end should not shrink.)
- It is disjoint if its start is > the anchor's end. Push it as a new block; it becomes the new anchor.
python
def merge(intervals):
    intervals.sort(key=lambda x: x[0])       # sort by START
    merged = []
    for start, end in intervals:
        if merged and start <= merged[-1][1]:      # overlaps or touches the anchor
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])            # disjoint: new block
    return merged

Sorting is O(N log N) and dominates; the sweep is O(N).

Crucial Notethe merge condition is start <= end, not start < end, because touching intervals count as connected here — [1,4] and [4,5] fuse into [1,5]. And the end update must be max(anchor_end, new_end), never just new_end. Consider anchor [1,10] meeting [2,3]: the [2,3] sits entirely inside, and blindly writing its end would wrongly shrink the block to [1,3]. Whether endpoints-touch counts as overlap is the first thing to confirm with an interviewer, since it flips that comparison.
Worked Example:[[1,3],[2,6],[8,10],[15,18]]
Already sorted by start.
- Anchor [1,3]. Result: [[1,3]].
- [2,6]: start 2 ≤ anchor end 3 → overlap. Extend end to max(3,6) = 6. Result: [[1,6]].
- [8,10]: start 8 > 6 → disjoint. New block. Result: [[1,6],[8,10]].
- [15,18]: start 15 > 10 → disjoint. New block. Result: [[1,6],[8,10],[15,18]].

Answer [[1,6],[8,10],[15,18]]. And the touching case [[1,4],[4,5]]: start 4 ≤ end 4, so they fuse into [[1,5]].

The pattern this establishes

This is the base template for almost every interval problem, and the move that unlocks it is worth stating on its own:

Sort the intervals first, and choose the sort key to make the interaction you care about local. Sorting by start makes "does this touch the running block?" a check against a single anchor. That is the same idea as the greedy interval problems — sort to turn a global tangle into a one-pass sweep — with a different key chosen for a different question.

Recognition signals: the input is a list of [start, end] ranges; the question involves overlap, coverage, gaps, or fusing. The reflex is sort by start for merging and coverage questions, and sort by end when you are selecting a maximum non-overlapping subset (as in Activity Selection and Non-overlapping Intervals). Getting the key right is 90% of solving these.

The immediate follow-ups build directly on this sweep. "Insert Interval" is this merge when the list is already sorted and only one new interval arrives. "Non-overlapping Intervals" flips the goal to deletion but reuses the sort-and-sweep skeleton. Once the sweep is in your hands, the family is variations on what you do at each step.

Interactive Strategy Visualization

Anchored Scan

0
2
4
6
8
10
12
Input
[1,3]
[2,6]
[8,10]
Merged
Let's consolidate these time ranges.
STRATEGY

Sort intervals by start time. Compare the current interval with the last one in the merged list.

DECISION

If curr.start \u2264 last.end, merge by updating last.end. Otherwise, add as new.

O(N²) Pairwise Merging
→
O(N log N) Time Sort plus Linear Sweep