Merge Intervals

Any problem about ranges — meeting times, calendar events, number ranges — that asks you to combine overlapping ones, insert a new one, or count how many you need, is a merge intervals problem. The trick that unlocks all of them: sort by start time first. Once intervals are sorted, overlaps only ever happen between neighbors, so a single pass is enough.

What you’ll learn

Why sorting by start time turns an $O(n^2)$ overlap check into $O(n \log n)$ total.
The merge template: compare each interval to the last one you kept.
Worked example: merging a list of overlapping intervals.
Related variants: inserting a new interval, and counting the minimum resources needed (meeting rooms).
The cue that says “sort by start, then sweep.”

The pattern

Sort intervals by their start value. Walk through them once, keeping a “merged” list. For each new interval, compare it only to the last interval you’ve kept: if they overlap, extend the last one; if not, append the new interval as its own entry.

merge_intervals_template.py

def merge_intervals(intervals):
    if not intervals:
        return []
 
    intervals = sorted(intervals, key=lambda pair: pair[0])
    merged = [intervals[0]]
 
    for start, end in intervals[1:]:
        last_start, last_end = merged[-1]
        if start <= last_end:                 # overlaps the last kept interval
            merged[-1] = [last_start, max(last_end, end)]
        else:                                  # no overlap -- start a new group
            merged.append([start, end])
 
    return merged
 
 
print(merge_intervals([[1, 3], [2, 6], [8, 10], [15, 18]]))

merge_intervals_template.py

def merge_intervals(intervals):
    if not intervals:
        return []
 
    intervals = sorted(intervals, key=lambda pair: pair[0])
    merged = [intervals[0]]
 
    for start, end in intervals[1:]:
        last_start, last_end = merged[-1]
        if start <= last_end:                 # overlaps the last kept interval
            merged[-1] = [last_start, max(last_end, end)]
        else:                                  # no overlap -- start a new group
            merged.append([start, end])
 
    return merged
 
 
print(merge_intervals([[1, 3], [2, 6], [8, 10], [15, 18]]))

How it works

Sorting guarantees that if interval ii doesn’t overlap the interval right before it, it can’t overlap anything even earlier either (their starts only get bigger). That’s what makes comparing to just the last kept interval enough — you never need to look further back.

diagram Sorted intervals collapsing into merged ranges mermaid

  graph LR
    A["[1,3]"] --> M1["overlaps [2,6] -> merge to [1,6]"]
    M1 --> B["[8,10] starts after 6 -> new group"]
    B --> C["[15,18] starts after 10 -> new group"]
    M1 --> R1["Result: [1,6]"]
    B --> R2["Result: [8,10]"]
    C --> R3["Result: [15,18]"]

sketch Overlapping intervals merging on a number line p5.js

Intervals are sorted by start. Each new interval either extends the current merged bar (overlap) or starts a fresh one (gap).

Worked example

Merge Intervals. The template above, applied directly.

merge_intervals.py

def merge_intervals(intervals):
    if not intervals:
        return []
 
    intervals = sorted(intervals, key=lambda pair: pair[0])
    merged = [intervals[0]]
 
    for start, end in intervals[1:]:
        last_start, last_end = merged[-1]
        if start <= last_end:
            merged[-1] = [last_start, max(last_end, end)]
        else:
            merged.append([start, end])
 
    return merged
 
 
print(merge_intervals([[1, 3], [2, 6], [8, 10], [15, 18]]))
# expect [[1, 6], [8, 10], [15, 18]]

merge_intervals.py

def merge_intervals(intervals):
    if not intervals:
        return []
 
    intervals = sorted(intervals, key=lambda pair: pair[0])
    merged = [intervals[0]]
 
    for start, end in intervals[1:]:
        last_start, last_end = merged[-1]
        if start <= last_end:
            merged[-1] = [last_start, max(last_end, end)]
        else:
            merged.append([start, end])
 
    return merged
 
 
print(merge_intervals([[1, 3], [2, 6], [8, 10], [15, 18]]))
# expect [[1, 6], [8, 10], [15, 18]]

Meeting Rooms II. A close relative: instead of merging, count the maximum overlap at any point in time — the fewest rooms needed. Sort start times and end times separately, then sweep both with two pointers: every time a meeting starts before the earliest one ends, you need another room.

meeting_rooms_ii.py

def min_meeting_rooms(intervals):
    starts = sorted(start for start, end in intervals)
    ends = sorted(end for start, end in intervals)
 
    rooms_needed = 0
    max_rooms = 0
    s = e = 0
 
    while s < len(starts):
        if starts[s] < ends[e]:
            rooms_needed += 1       # a new meeting starts before one ends
            s += 1
        else:
            rooms_needed -= 1       # a meeting ended, free up a room
            e += 1
        max_rooms = max(max_rooms, rooms_needed)
 
    return max_rooms
 
 
print(min_meeting_rooms([[0, 30], [5, 10], [15, 20]]))   # expect 2

meeting_rooms_ii.py

def min_meeting_rooms(intervals):
    starts = sorted(start for start, end in intervals)
    ends = sorted(end for start, end in intervals)
 
    rooms_needed = 0
    max_rooms = 0
    s = e = 0
 
    while s < len(starts):
        if starts[s] < ends[e]:
            rooms_needed += 1       # a new meeting starts before one ends
            s += 1
        else:
            rooms_needed -= 1       # a meeting ended, free up a room
            e += 1
        max_rooms = max(max_rooms, rooms_needed)
 
    return max_rooms
 
 
print(min_meeting_rooms([[0, 30], [5, 10], [15, 20]]))   # expect 2

Time and space complexity

Step	Time	Space
Sort by start	$O(n \log n)$	$O(n)$ (or $O(\log n)$ for the sort itself)
Single merge pass	$O(n)$	$O(n)$ for the output
Total	$O(n \log n)$	$O(n)$

The sort dominates the runtime — once intervals are ordered, merging itself is linear.

When to use it

Cue in the problem	Approach
“merge all overlapping intervals”	Sort by start, sweep once
“insert a new interval into a sorted list”	Skip / merge / append in one pass
“minimum number of meeting rooms / resources”	Sort starts and ends separately, sweep both
“can a person attend all meetings”	Sort by start, check consecutive overlap
“count non-overlapping intervals to remove”	Sort by end time, greedily keep earliest-ending

Practice — real LeetCode problems

Each exercise is the actual LeetCode problem with its real method signature and LeetCode’s own examples as the test. Write the body, press Run, and match the expected output.

LC 56 — Merge Intervals · Medium

Problem. Given an array of intervals, merge all overlapping intervals and return the non-overlapping intervals that cover the same ranges.

Constraints. 1 <= len(intervals) <= 10^41 <= len(intervals) <= 10^4, 0 <= start <= end <= 10^40 <= start <= end <= 10^4.

Examples. [[1,3],[2,6],[8,10],[15,18]][[1,3],[2,6],[8,10],[15,18]] gives [[1,6],[8,10],[15,18]][[1,6],[8,10],[15,18]] · [[1,4],[4,5]][[1,4],[4,5]] gives [[1,5]][[1,5]]

Editorial

Sorting by start is the enabling step: after it, any interval that overlaps the one you are building must be the very next one, so a single pass suffices.

Time $O(n \log n)$ for the sort. Space $O(n)$ for the output.

Two details:

max(out[-1][1], end)max(out[-1][1], end), not = end= end. [[1,4],[2,3]][[1,4],[2,3]] has the second interval entirely inside the first, so assigning would shrink the merged range to [1,3][1,3]. The test includes it for that reason.
start <= out[-1][1]start <= out[-1][1] treats touching intervals as overlapping, so [[1,4],[4,5]][[1,4],[4,5]] merges to [[1,5]][[1,5]]. Whether touching counts is a genuine clarifying question — LC 56 says it does.

Contrast with sorting by end, which is what interval scheduling needs. Merging wants start order; selecting a maximum non-overlapping subset wants end order. Same input shape, different sort, different problem.

Follow-ups: “Insert one interval into an already-sorted list (LC 57)?” — next problem: no sort needed, $O(n)$ . “Count the rooms needed instead?” — that is a sweep line, not a merge. “Intervals arriving as a stream?” — keep them in a sorted structure and merge on insert.

LC 57 — Insert Interval · Medium

Problem. Given a list of non-overlapping intervals sorted by start, insert a new interval, merging where necessary. Return the result still sorted and non-overlapping.

Constraints. 0 <= len(intervals) <= 10^40 <= len(intervals) <= 10^4, sorted and non-overlapping, 0 <= start <= end <= 10^50 <= start <= end <= 10^5.

Examples. intervals = [[1,3],[6,9]], newInterval = [2,5]intervals = [[1,3],[6,9]], newInterval = [2,5] gives [[1,5],[6,9]][[1,5],[6,9]] · intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] gives [[1,2],[3,10],[12,16]][[1,2],[3,10],[12,16]]

Editorial

Because the input is already sorted and non-overlapping, this is $O(n)$ rather than LC 56’s $O(n \log n)$ . Exploiting the guarantee you were given is the point.

Time $O(n)$ . Space $O(n)$ .

The three phases partition the intervals cleanly:

Ends before the new one starts (intervals[i][1] < startintervals[i][1] < start) — untouched.
Starts at or before the new one ends (intervals[i][0] <= endintervals[i][0] <= end) — overlaps, so absorb it by widening startstart and endend. Note the new interval keeps growing as it absorbs, which is why later intervals can also be pulled in — that is how [4,8][4,8] ends up as [3,10][3,10] in the second example.
Everything after — untouched.

Both boundary comparisons are non-strict on the touching case, matching LC 56’s convention.

([], [5,7])([], [5,7]) and ([[1,5]], [6,8])([[1,5]], [6,8]) are the degenerate cases: an empty list, and a new interval that overlaps nothing.

Follow-ups: “Why no sort?” — the input guarantee; this is the expected question. “Insert many intervals?” — repeated insertion is $O(nm)$ ; better to concatenate and run LC 56 once. “Remove an interval instead (LC 1272)?” — similar three-phase walk, splitting rather than merging. “Binary search for the start phase?” — yes, $O(\log n)$ to find it, though the absorb phase is still $O(n)$ in the worst case.

LC 986 — Interval List Intersections · Medium

Problem. Given two lists of closed intervals, each sorted and pairwise disjoint, return the intersection of the two lists.

Constraints. 0 <= len(each list) <= 10000 <= len(each list) <= 1000, both sorted and disjoint, 0 <= start <= end <= 10^90 <= start <= end <= 10^9.

Examples. first = [[0,2],[5,10],[13,23],[24,25]]first = [[0,2],[5,10],[13,23],[24,25]], second = [[1,5],[8,12],[15,24],[25,26]]second = [[1,5],[8,12],[15,24],[25,26]] gives [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]][[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

Editorial

The intersection of [a1, a2][a1, a2] and [b1, b2][b1, b2] is [max(a1,b1), min(a2,b2)][max(a1,b1), min(a2,b2)], which is non-empty exactly when max(starts) <= min(ends)max(starts) <= min(ends).

Time $O(m + n)$ . Space $O(m + n)$ for the output.

The advancement rule is the crux: advance whichever interval ends first. Since both lists are sorted and disjoint, an interval that ends earlier cannot possibly overlap any later interval in the other list — so it is finished and can be discarded. Advancing the wrong pointer skips intersections.

Note the output can contain single-point intervals like [5,5][5,5] and [24,24][24,24], because these are closed intervals — [5,10][5,10] and [1,5][1,5] share exactly the point 5. The lo <= hilo <= hi test (not <<) is what keeps them. That is easy to get wrong, and those two entries in the first example exist to catch it.

([[1,3],[5,9]], [])([[1,3],[5,9]], []) returning [][] handles an empty list with no special case, since the loop condition fails immediately.

Follow-ups: “Union instead of intersection?” — concatenate and run LC 56. “Why advance the earlier-ending one?” — the sortedness argument; the expected question. “Half-open intervals?” — the test becomes lo < hilo < hi and single points disappear. “More than two lists?” — fold pairwise, or sweep all endpoints at once.

LeetCode problem set

#	Problem	Difficulty	The twist
56	Merge Intervals	Medium	Sort by start, then extend or append — the base template for the whole family
57	Insert Interval	Medium	Already sorted, so merge in one pass without sorting: before, overlapping, after
435	Non-overlapping Intervals	Medium	Greedy the other way — sort by end and keep the earliest-finishing compatible interval
253	Meeting Rooms II	Medium · Premium	Only the count of overlaps matters, so a min-heap of end times (or a sweep line) beats merging

Recap

Sort intervals by start time first — that’s what guarantees you only ever need to compare a new interval to the last merged one.
The merge pass itself is $O(n)$ ; the sort dominates at $O(n \log n)$ total.
Insert Interval skips the sort (input’s already sorted); Meeting Rooms II sorts starts and ends separately and sweeps both with two pointers.
Cue: any “overlapping ranges” problem — merge, insert, count, or schedule — starts with sort-by-start.

Next: Cyclic Sort — placing numbers 1..n1..n directly at their home index to find missing or duplicate values in $O(n)$ with no extra space.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Merge Intervals

What you’ll learn

The pattern

How it works

Worked example

Time and space complexity

When to use it

Practice — real LeetCode problems

LC 56 — Merge Intervals · Medium

LC 57 — Insert Interval · Medium

LC 986 — Interval List Intersections · Medium

LeetCode problem set

Recap

Was this page helpful?