How-to Intermediate

Chapter 1 Updated April 21, 2026

Merge Intervals

Sort by start, merge adjacent overlaps in one pass.

Full 6m
Revision 2m
Flow 2m

LeetCode #56 — one-liner.

Given a list of intervals with possible overlaps, return the minimum non-overlapping set that covers the same ranges.

Sort + one-pass merge.

After sorting by start, any overlapping intervals sit next to each other.
Maintain a running “last merged” — extend its end if the next interval’s start ≤ last end, otherwise start a new bucket.
Containment handled for free by end = max(last.end, current.end).

The six lines that matter.

intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for s, e in intervals[1:]:
    if s <= merged[-1][1]:
        merged[-1][1] = max(merged[-1][1], e)
    else:
        merged.append([s, e])

Sort bound, nothing else.

Time O(n log n) — sort dominates; the scan is linear.
Space O(n) — output list (input may or may not sort in-place).

The ones that trip people up.

Empty input → return [] before touching the list.
Single interval → trivial passthrough.
Touching endpoints [1,2] + [2,3] → merge because 2 ≤ 2 (note ≤, not <).
One interval fully contains another → max on end handles it.

Comments

Comments are disabled in this environment. Set PUBLIC_GISCUS_REPO, PUBLIC_GISCUS_REPO_ID, and PUBLIC_GISCUS_CATEGORY_ID to enable.