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
Recognise the pattern
The signal is “intervals” + “merge/overlap”. Interval problems almost always start with the same move: sort by start time. Once sorted, any overlap can only happen between consecutive intervals — you never need to look back more than one step. This reduces a problem that looks quadratic into a single linear scan.
Build the approach step by step
Without sorting: you’d have to compare every interval against every other: O(n²).
The sort-then-scan approach:
- Sort
intervalsby each interval’s start value. - Put the first interval in your
mergedlist. - For each subsequent interval
[s, e]:- If
s <= merged[-1][1](it overlaps or touches the last merged interval), extend:merged[-1][1] = max(merged[-1][1], e). - Otherwise, it’s completely disjoint — append it as a new entry.
- If
Why max(merged[-1][1], e)? Because one interval can be fully contained inside another. Example: [1,10] followed by [2,5] — after sorting, the second is contained in the first, so we keep the end as 10, not shrink it to 5.
Walk through [[1,3],[2,6],[8,10],[15,18]]:
- Start with
[[1,3]] [2,6]:2 <= 3→ merge →[[1,6]][8,10]: 8>6 → new →[[1,6],[8,10]][15,18]: 15>10 → new →[[1,6],[8,10],[15,18]]
Complexity
- Time — O(n log n): dominated by the sort. The merge scan is O(n).
- Space — O(n): the output list holds at most n intervals (when none overlap).