Merge Intervals
Given a list of intervals, merge all overlapping ones and return the non-overlapping result.
Open on LeetCode ↗Intuition
Sort intervals by start. Then sweep left to right: if the next interval begins before the current merged block ends, they overlap — extend the block's end. Otherwise start a fresh block.
Almost every interval problem starts with a sort, and the choice of key is the whole puzzle. Sort by start when you're merging or inserting — it guarantees that anything overlapping the current block appears next, so one pass suffices. Sort by end when you're packing the most non-overlapping items in (the classic greedy scheduling move). If you can't decide, ask what the greedy choice is: merging cares about what begins next, scheduling cares about what frees up soonest.
Approach
Pairwise comparison is messy and slow
Comparing every interval against every other for overlap is O(n²), and merging gets tangled because merging two intervals can create a new one that overlaps a third — the merges chain in unpredictable order. We need to impose structure so each interval only ever interacts with one neighbor.
Sort by start, and overlaps become local
Sort the intervals by their start value. Now any interval can only overlap the block immediately before it — never something far behind — because everything earlier started earlier and has already been settled. This collapses the O(n²) tangle into a single left-to-right sweep that compares each interval to just the most recent merged block.
Extend or append, one pass
Seed the result with the first interval. For each subsequent (start, end): if start <= last.end, they overlap, so absorb it by extending last.end = max(last.end, end) (the max matters when one interval fully contains another). Otherwise there's a gap, so start a new block. Using <= makes touching intervals like [1,4] and [4,5] merge. Dominated by the sort: O(n log n) time, O(n) output.
Solution & live demo
Common pitfalls
Sorting by end time
intervals.sort(key=lambda x: x[1])
intervals.sort(key=lambda x: x[0])
With [[1, 10], [2, 3], [4, 5]], sorting by end gives [2,3], [4,5], [1,10] — the wide interval that swallows both arrives last, so neither earlier block gets merged into it. Sorting by start makes overlaps adjacent.
Extending with end instead of max
if start <= res[-1][1]:
res[-1][1] = endif start <= res[-1][1]:
res[-1][1] = max(res[-1][1], end)A fully-contained interval shrinks the block it lands in: [1, 10] followed by [2, 3] becomes [1, 3], silently dropping everything from 3 to 10. Sorting by start orders the left edges only — it says nothing about which right edge is larger.
Using < and missing exact touches
if start < res[-1][1]:
if start <= res[-1][1]:
[1, 4] and [4, 5] share the endpoint 4, and LeetCode counts that as overlapping — the expected answer is [1, 5], not two intervals. Strict < treats touching as disjoint.
Edge cases
start <= last.end is true at equality, so adjacent intervals merge into [1,5].
max(last.end, end) keeps the larger end, so the inner interval is absorbed.
No start <= last.end ever holds, so each interval is appended unchanged.