Patternwise

Merge Intervals

Sort by start, then only compare with the last one.

Brute force
O(n²) — compare every pair, repeatedly
With the pattern
O(n log n) — sort, then one linear pass
Extra space
O(n) — output (O(log n)–O(n) for the sort)

In plain English

“You're combining everyone's meeting times onto one calendar. If you lay the meetings out in order of start time, you only ever need to ask, "does this meeting start before the last block I wrote down ends?" If yes, stretch that block; if no, start a new one.”

Why it's fast

Unsorted, any interval might overlap any other, so you'd compare all pairs (O(n²)). After sorting by start, an interval can only overlap the most recent merged block — everything earlier already ended. That turns merging into a single linear pass after an O(n log n) sort.

Spot it when the problem says…

  • list of intervals [start, end]
  • merge overlapping
  • insert a new interval
  • minimum number of rooms / arrows / removals
  • free time / gaps between meetings
  • intersection of two interval lists

Visualize

Merge overlapping intervals

Merge all overlapping intervals and return the non-overlapping result.

[8,10]
[1,3]
[15,18]
[2,6]
[9,12]
[17,20]
merged
1234567891011121314151617181920
01/12

Unsorted, overlaps are hard to see — they could be anywhere.

pythonline 1
1def merge(intervals):2    intervals.sort(key=lambda iv: iv[0])3    merged = [intervals[0]]4    for start, end in intervals[1:]:5        last = merged[-1]6        if start <= last[1]:              # overlaps7            last[1] = max(last[1], end)   # stretch it8        else:9            merged.append([start, end])   # gap: new block10    return merged

How to apply it

  1. 01Sort intervals by start (or by end for greedy 'max non-overlapping' questions).
  2. 02Start the output with the first interval.
  3. 03For each next interval: if start <= last_end, extend last_end = max(last_end, end).
  4. 04Otherwise append it as a new block.

Variations you'll meet

Merge overlapping

The visualizer's example.

python
def merge(intervals: list[list[int]]) -> list[list[int]]:    intervals.sort(key=lambda iv: iv[0])    out = [intervals[0][:]]    for start, end in intervals[1:]:        if start <= out[-1][1]:             # overlaps last block            out[-1][1] = max(out[-1][1], end)        else:            out.append([start, end])    return out

Max non-overlapping (sort by end)

Greedy: always keep the interval that finishes earliest. Answers Non-overlapping Intervals and Minimum Arrows.

python
def erase_overlap_intervals(intervals: list[list[int]]) -> int:    intervals.sort(key=lambda iv: iv[1])    kept, last_end = 0, float("-inf")    for start, end in intervals:        if start >= last_end:            kept += 1            last_end = end    return len(intervals) - kept

Sweep line / min rooms

Turn each interval into +1 at start and -1 at end, sort events, track the running max. A min-heap of end times works too.

Two-list intersection

Two pointers over two sorted lists; overlap is [max(starts), min(ends)]; advance the one that ends first.

Common mistakes

  • Forgetting to sort first.
  • Setting last_end = end instead of max(last_end, end) — a short interval inside a long one shrinks the block.
  • Getting touching intervals wrong: is [1,2] and [2,3] an overlap? Read the problem (<= vs <).
  • Mutating the input lists you appended to the output, aliasing bugs when the caller reuses them.

Practice ladder

Easy → hard. Tick them off as you go.

0/8 solved
  1. 01Summary Ranges ↗Easy
  2. 02Merge Intervals ↗Medium
  3. 03Insert Interval ↗Medium
  4. 04Non-overlapping Intervals ↗Medium
  5. 05Minimum Number of Arrows to Burst Balloons ↗Medium
  6. 06Interval List Intersections ↗Medium
  7. 07Car Pooling ↗Medium
  8. 08Data Stream as Disjoint Intervals ↗Hard

Think you've got it?

Let the AI interviewer throw a Merge Intervals problem at you and grade how you explain it.

Mock interview