Given a list of intervals, merge all overlapping intervals and return the result.
Sort intervals by start time. Then walk through them once: if the current interval's start is at or before the end of the last merged interval, merge by extending the end. Otherwise, the current interval is disjoint — push it onto the result. Sorting costs O(n log n); the merge pass is O(n).
How to think about it
The two words that should trigger the reflex here are “intervals” and “overlap.” Almost every interval problem opens with the same move, and the interviewer wants to see you make it without prompting: sort by start time. The reason is worth saying out loud. Once the intervals are sorted, any overlap can only happen between neighbours — you never have to look back more than one step. That single insight turns a problem that smells O(n²) (compare everyone to everyone) into one sort plus one linear sweep.
After sorting, you carry a running list of merged intervals and walk the rest. For each interval [s, e], you ask one question: does its start fall at or before the end of the last merged interval? If yes, they touch or overlap, so you stretch the last interval’s end outward. If no, there’s a clean gap, and this interval starts a fresh entry. The one subtlety is how you stretch: you take max(last_end, e), not just e, because a short interval can sit entirely inside a long one — [1,10] swallowing [2,5] — and you must not let it shrink the end back to 5.
A worked example
def merge_intervals(intervals):
if not intervals:
return []
intervals.sort(key=lambda x: x[0]) # sort by start — the whole trick
merged = [intervals[0]]
for start, end in intervals[1:]:
if start <= merged[-1][1]:
# overlaps or touches: stretch the end, never shrink it
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end]) # clean gap: new interval
return merged
print(merge_intervals([[1,3],[2,6],[8,10],[15,18]])) # two overlap, two stand alone
print(merge_intervals([[1,4],[4,5]])) # touching at 4
print(merge_intervals([[1,4],[2,3]])) # one contains the other
print(merge_intervals([[5,10]])) # single interval[[1, 6], [8, 10], [15, 18]]
[[1, 5]]
[[1, 4]]
[[5, 10]]In the first list, [1,3] and [2,6] overlap and fuse into [1,6], while [8,10] and [15,18] have gaps before them and survive untouched. [1,4] and [4,5] merely touch at 4, and because the test is <=, they still merge into [1,5]. The third case is the containment trap: [2,3] lives wholly inside [1,4], so the max keeps the end at 4 rather than collapsing it to 3.