Given an array of intervals, merge every pair of intervals that overlap and return the resulting set of non-overlapping intervals.
Example
Input intervals = [[1,3],[2,6],[8,10],[15,18]]
Output [[1,6],[8,10],[15,18]]
Key Pointers
Sorting by start time first turns "any pair might overlap" into "only neighbors in the sorted order can overlap" — that's what makes one linear pass afterward sufficient.
Two intervals overlap when the next one's start is at or before the current merged interval's end.
Always compare against the last interval already placed in the result, not the original array — it may have grown from earlier merges.
Step-by-Step Analysis
Sort intervals by start time.
Seed the result with the first interval.
For each subsequent interval, if its start is at or before the end of the last interval in the result, merge by extending that interval's end to the max of the two ends.
Otherwise, it doesn't overlap — append it as a new separate interval.
Complexity
Time: O(n log n) for the sort — Space: O(n)
Code
def merge(intervals: list[list[int]]) -> list[list[int]]:
intervals.sort(key=lambda x: x[0])
result = [intervals[0]]
for start, end in intervals[1:]:
last = result[-1]
if start <= last[1]:
last[1] = max(last[1], end)
else:
result.append([start, end])
return result
Code Explanation
How the solution above works, piece by piece.
Sort by start so overlapping intervals are next to each other.
result starts with the first interval.
If the next interval starts at or before the last merged interval's end, they overlap: extend the end to max(last[1], end). Using max handles an interval fully inside another.
Otherwise it begins a new merged interval.
O(n log n) for the sort, O(n) for the scan.
Visual Walkthrough
Running it on intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]:
After sorting by start, an interval overlaps the last merged one exactly when it starts before that one ends. [2, 6] starts at 2 ≤ 3, so [1, 3] stretches to [1, 6]; the others start after the previous end and are appended.