Merge Intervals — Coding Interview Patterns

Any time you see [start, end] pairs and the word “overlapping”, this is your pattern. The entire insight is one line: sort by start time first.

The idea

Once the intervals are sorted by start, overlaps can only happen between adjacent intervals in that order. So you sweep left to right keeping a “current” merged interval:

If the next interval starts before the current one ends (next.start ≤ current.end), they overlap → extend current.end = max(current.end, next.end).
Otherwise there’s a gap → close the current interval and start a new current from the next one.

One sort (O(n log n)) plus one linear pass. The sort is the expensive and essential step.

The template

def merge(intervals):
    intervals.sort()                       # sort by start (then end)
    out = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= out[-1][1]:            # overlaps current → extend
            out[-1][1] = max(out[-1][1], end)
        else:                              # gap → new interval
            out.append([start, end])
    return out
# merge([[1,3],[2,6],[8,10],[15,18]]) -> [[1,6],[8,10],[15,18]]

Worked example: insert interval

Insert a new interval into an already-sorted, non-overlapping list and merge. Three phases — intervals entirely before, the overlapping block, and intervals entirely after:

def insert(intervals, new):
    res = []; i = 0; n = len(intervals)
    # 1. all intervals ending before new starts
    while i < n and intervals[i][1] < new[0]:
        res.append(intervals[i]); i += 1
    # 2. merge all that overlap new
    while i < n and intervals[i][0] <= new[1]:
        new = [min(new[0], intervals[i][0]), max(new[1], intervals[i][1])]
        i += 1
    res.append(new)
    # 3. the rest
    while i < n:
        res.append(intervals[i]); i += 1
    return res
# insert([[1,3],[6,9]], [2,5]) -> [[1,5],[6,9]]

“What is the maximum number of intervals overlapping at once?” (minimum meeting rooms) is a cousin. Two clean approaches: a min-heap of end times (pop a room when a meeting starts after it ends), or a sweep line of +1 at each start and −1 at each end, sorted by time, tracking the running maximum. Both are O(n log n).

Step-by-step walkthrough

Trace Merge Intervals on [[1, 3], [8, 10], [2, 6], [15, 18], [17, 20]]. First sort by start: [[1, 3], [2, 6], [8, 10], [15, 18], [17, 20]]. Then sweep once, comparing each interval with the last merged one.

current	decision	merged so far
[1, 3]	no overlap → start new	[[1, 3]]
[2, 6]	overlaps [1, 3] → extend to [1, 6]	[[1, 6]]
[8, 10]	no overlap → start new	[[1, 6], [8, 10]]
[15, 18]	no overlap → start new	[[1, 6], [8, 10], [15, 18]]
[17, 20]	overlaps [15, 18] → extend to [15, 20]	[[1, 6], [8, 10], [15, 20]]

Sorting puts every overlap next to each other, so a single sweep suffices — O(n log n) for the sort. Result: [[1, 6], [8, 10], [15, 20]].

When to reach for it

Signals: the input is a list of [start, end] pairs; the words overlap, merge, meeting, booking, schedule, interval appear. If the question is about ranges on a line, sorting by start (or by endpoint events) is almost always step one.

Pitfalls

Forgetting to sort. Without sorting by start, adjacent-overlap logic is wrong. This is the #1 mistake.
Boundary < vs ≤. Decide whether touching intervals like [1,2] and [2,3] count as overlapping for this problem and use the matching comparison.
Mutating while iterating. Build a new output list; don’t modify the list you’re sweeping.

Recap

For overlapping-range problems, sort by start, then sweep keeping a current interval: extend it when the next starts before it ends, otherwise start a new one — O(n log n). Insert-interval is the same idea in three phases; max-overlap (meeting rooms) uses a heap or sweep line. Signal: [start,end] pairs + overlap/merge/schedule.

Practice: 10 solved problems on merge intervals → — cover each one, solve it yourself, then check the tested code.

Next: Lesson 9 — Monotonic Stack, for next-greater-element problems.