Sorting first turns an O(n²) overlap-check problem into an O(n log n) single-pass greedy solution.
Given a list of intervals, merge all overlapping intervals and return the result.
# [[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]]
# [1,3] and [2,6] overlap (2 ≤ 3) → merged to [1,6]
#
# [[1,4],[4,5]] → [[1,5]]
# Intervals that touch at a single point are considered overlapping.Without sorting, you'd have to compare every interval against every other — O(n²). Once sorted by start time, you only ever need to compare each new interval against the last merged interval. No interval before that can overlap with the current one.
# After sorting by start: [1,3] [2,6] [8,10] [15,18]
#
# [1,3] → start the merge list. result: [[1,3]]
# [2,6] → 2 ≤ 3, overlaps! Extend end to max(3,6)=6. result: [[1,6]]
# [8,10]→ 8 > 6, no overlap. Add new interval. result: [[1,6],[8,10]]
# [15,18]→ 15 > 10, no overlap. Add new. result: [[1,6],[8,10],[15,18]]def merge(intervals):
intervals.sort(key=lambda x: x[0]) # Sort by start time
merged = [intervals[0]]
for start, end in intervals[1:]:
last_end = merged[-1][1]
if start <= last_end:
# Overlapping — extend the last interval's end
merged[-1][1] = max(last_end, end)
else:
# Gap — start a new interval
merged.append([start, end])
return merged
print(merge([[1,3],[2,6],[8,10],[15,18]])) # [[1,6],[8,10],[15,18]]
print(merge([[1,4],[4,5]])) # [[1,5]]| Property | Value |
|---|---|
| Time | O(n log n) — dominated by the sort |
| Space | O(n) — output list |
max(last_end, end) handles the case where one interval completely contains the next — e.g., [1,10] followed by [2,5]. Without the max, you'd incorrectly shrink the end to 5.Input: [[1,3],[2,6],[8,10],[15,18]] (already sorted)
| Current | Last merged end | Overlap? | Result |
|---|---|---|---|
| [1,3] | — (first) | — | [[1,3]] |
| [2,6] | 3 | 2 ≤ 3 ✓ | [[1,6]] |
| [8,10] | 6 | 8 > 6 ✗ | [[1,6],[8,10]] |
| [15,18] | 10 | 15 > 10 ✗ | [[1,6],[8,10],[15,18]] |