# The sort-then-sweep trick behind merge intervals

Source: https://www.techinterview.org/post/3233476037/merge-intervals-sort-then-sweep/
Updated: 2026-07-02 · techinterview.org

Sort the intervals by their start, then walk through them once while keeping a single "current" interval open. That is the entire algorithm for LeetCode 56, and once it clicks you have most of an interview category in your pocket. The hard part was never the merge. It was seeing that sorting is what makes overlaps line up next to each other, so a single pass can find them.

Here is the problem the way it actually gets asked. You're given a list like `[[1,3],[2,6],[8,10],[15,18]]` and asked to return the non-overlapping intervals that cover the same ground: `[[1,6],[8,10],[15,18]]`. The interviewer might dress it up as calendar events, IP address ranges, or positions on a genome, but the shape is identical every time.

## The sweep

After sorting by start time, two intervals overlap only if the next one begins at or before the current one ends. When it does, you stretch the current interval's end to cover both. When it doesn't, the current interval is finished, and you start a new one against the next element.


```
def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    out = []
    for start, end in intervals:
        if out and start <= out[-1][1]:
            out[-1][1] = max(out[-1][1], end)
        else:
            out.append([start, end])
    return out
```


The `max` on that one line is the part candidates drop under pressure. A naive version writes `out[-1][1] = end`, which breaks on input like `[[1,5],[2,3]]`: the second interval ends earlier, so blindly assigning shrinks your merged interval to `[1,3]` and you quietly lose coverage. Sorted order guarantees starts are non-decreasing, but it promises nothing about ends, so you always keep the larger end. The same logic handles fully nested intervals like `[[1,10],[2,3],[4,5]]` without any special case, which is a good thing to point out before the interviewer asks.

The cost is `O(n log n)` for the sort plus `O(n)` for the walk, so the sort dominates and the whole thing is `O(n log n)` time and `O(n)` extra space for the output. If someone asks whether you can beat that bound, the answer is no in the comparison model, unless the inputs already arrive sorted or the endpoints are bounded integers you can bucket. Saying that out loud reads better than hoping nobody asks.

## The line that hides a real question

That `<=` is a decision, not a default. With `<=`, the touching intervals `[1,4]` and `[4,5]` merge into `[1,5]`. With `<`, they stay separate. Which one is right depends entirely on what the intervals represent. Closed numeric ranges that share an endpoint usually should merge. Back-to-back meetings, where one ends at 4:00 and the next starts at 4:00, usually should not count as a conflict. Decent candidates notice the ambiguity. The strong ones state an assumption out loud ("I'll treat shared endpoints as overlapping, tell me if that's wrong") and keep coding instead of freezing on it.

## Why this one pattern keeps coming back

Interval questions feel repetitive because they are. Sort by a sensible key, sweep once, carry a small amount of state. The state is the only thing that really changes from problem to problem.

| Problem | Sort key | State you carry | Answer |
| --- | --- | --- | --- |
| Merge Intervals (56) | start | the open merged interval | merged list |
| Insert Interval (57) | already sorted | one growing new interval | merged list |
| Meeting Rooms II (253) | starts and ends, separately | count of open meetings | max count |
| Interval List Intersections (986) | already sorted, two pointers | front interval of each list | intersections |
| Employee Free Time (759) | start, after flattening | the open merged block | gaps between blocks |

Take Insert Interval (LeetCode 57). The list is already sorted and non-overlapping, and you're handed one new interval to fold in. You don't re-sort. You walk in three stretches: copy every interval that ends before the new one starts, merge everything that overlaps the new one by widening its bounds, then copy the rest.


```
def insert(intervals, new):
    out, i, n = [], 0, len(intervals)
    while i < n and intervals[i][1] < new[0]:
        out.append(intervals[i]); i += 1
    while i < n and intervals[i][0] <= new[1]:
        new = [min(new[0], intervals[i][0]), max(new[1], intervals[i][1])]
        i += 1
    out.append(new)
    out.extend(intervals[i:])
    return out
```


Because the input is pre-sorted, this runs in `O(n)`. An interviewer who watches you reach for `.sort()` here is quietly noting that you didn't read the constraints.

### Meeting Rooms II asks a different question of the same data

Meeting Rooms II (LeetCode 253) wants the minimum number of rooms to hold every meeting, which equals the maximum number of intervals overlapping at any single instant. The merge skeleton doesn't answer that directly, but the sort-then-sweep instinct still wins. Pull the starts and ends into separate arrays, sort each, then sweep one pointer: every time a meeting begins before the earliest still-open meeting ends, you needed another room.


```
def min_meeting_rooms(intervals):
    starts = sorted(i[0] for i in intervals)
    ends = sorted(i[1] for i in intervals)
    rooms = used = e = 0
    for s in starts:
        if s < ends[e]:
            used += 1
            rooms = max(rooms, used)
        else:
            e += 1
    return rooms
```


The min-heap version, where you push end times and pop whenever a room frees up, is the one most people memorize. It's correct and fine to present. The two-sorted-arrays sweep is faster to write and easier to reason about when the clock is running, and both land at `O(n log n)`. I'd lead with the sweep and mention the heap as the alternative.

## The variant Meta likes to ask

A recurring one at Meta is Interval List Intersections (LeetCode 986): two already-sorted lists of disjoint intervals, return everywhere they overlap. Two pointers, one per list. The intersection of the two front intervals, when it exists, is `[max(the starts), min(the ends)]`. Then advance the pointer whose interval ends first, since it can't intersect anything further down the other list.


```
def interval_intersection(a, b):
    i = j = 0
    out = []
    while i < len(a) and j < len(b):
        lo = max(a[i][0], b[j][0])
        hi = min(a[i][1], b[j][1])
        if lo <= hi:
            out.append([lo, hi])
        if a[i][1] < b[j][1]:
            i += 1
        else:
            j += 1
    return out
```


No sort anywhere, because the inputs arrive sorted. That absence is the tell the problem is testing: do you notice when the expensive step has already been done for you. Employee Free Time (LeetCode 759) is the next rung up the same ladder. Flatten everyone's intervals into one list, sort once, sweep, and report the gaps that fall between the merged blocks.

## What interviewers push on after you solve it

Solving Merge Intervals cleanly buys you about ninety seconds before the follow-ups start, so it pays to have answers ready for the usual ones.

Can you do it in place? Yes. Sort the array and overwrite from the left with a write pointer, since the merged result is never longer than the input. You save the output allocation, but the sort still costs `O(n log n)`, so the asymptotic bound doesn't move.

What if the intervals stream in and never stop? Now you can't sort the whole input, so you keep a structure of disjoint intervals, a balanced BST or an ordered map keyed by start, and merge each arrival against its neighbors in `O(log n)`. That's the LeetCode 715 problem, Range Module, and it's where the easy question turns into a small system-design problem about which operations you have to support.

What if the coordinates are huge and sparse, like millisecond timestamps spread across a year? Coordinate compression, or an interval tree if you also need point queries rather than just the merged set. Naming the option is usually enough; you rarely have to code it on the spot.

The thing to take away is that merging intervals isn't a problem you memorize, it's a default move. When a question hands you a pile of ranges and asks anything about overlap, coverage, gaps, or scheduling conflicts, your first instinct should be to sort by start and sweep, and you reach for a heap or a tree only when the plain sweep can't carry the weight. Build that reflex and a whole column of the LeetCode grid stops looking like separate problems.