LeetCode #56 Medium

Merge Intervals

Given a list of intervals, merge all overlapping ones and return the non-overlapping result.

arraysortingintervals

02

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.

03

Approach

1

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.

2

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.

3

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.

04

Solution & live demo

python

▶1class Solution:
▶2    def merge(self, intervals):
▶3        intervals.sort(key=lambda x: x[0])
▶4        res = [intervals[0]]
▶5        for start, end in intervals[1:]:
▶6            if start <= res[-1][1]:
▶7                res[-1][1] = max(res[-1][1], end)
▶8            else:
▶9                res.append([start, end])
▶10        return res

05

Edge cases

Touching intervals, e.g. [1,4],[4,5]

start <= last.end is true at equality, so adjacent intervals merge into [1,5].

One interval engulfs another, e.g. [1,10],[2,3]

max(last.end, end) keeps the larger end, so the inner interval is absorbed.

Already disjoint and sorted

No start <= last.end ever holds, so each interval is appended unchanged.

06

Complexity

Time

O(n log n)

Space

O(n)

Dominated by the sort; the sweep is linear.