Learning Outcome
After this lesson, you should be able to sort intervals by start and maintain one active merged interval.
Problem Statement
Given a list of intervals, merge all overlapping intervals and return the non-overlapping result.
| Input | Output | Why |
|---|---|---|
intervals = [[1,3],[2,6],[8,10],[15,18]] | [[1,6],[8,10],[15,18]] | [1,3] overlaps [2,6], so they merge into [1,6]. |
Brute Force Approach
Repeatedly compare every interval with every other interval until no merges remain. This is slow and easy to get wrong.
Optimized Approach
Sort intervals by start. Sweep from left to right and merge into the last interval when starts overlap.
Exact Pseudocode
sort intervals by start
merged = []
for interval in intervals:
if merged is empty or interval.start > merged.last.end:
add interval to merged
else:
merged.last.end = max(merged.last.end, interval.end)
return mergedReference Code
class Solution:
def merge(self, intervals):
intervals.sort(key=lambda x: x[0])
merged = []
for start, end in intervals:
if not merged or start > merged[-1][1]:
merged.append([start, end])
else:
merged[-1][1] = max(merged[-1][1], end)
return mergedSample Dry Run
| Step | State | Result |
|---|---|---|
| Sort | Intervals already sorted by start | Ready to sweep |
| [1,3] | merged is empty | add [1,3] |
| [2,6] | 2 <= 3 | merge to [1,6] |
| [8,10] | 8 > 6 | start new interval |
Complexity
| Measure | Value | Reason |
|---|---|---|
| Time | O(n log n) | Sorting dominates the runtime. |
| Space | O(n) | The merged output can store all intervals. |
Edge Cases
- Touching intervals like [1,4] and [4,5] usually merge.
- An empty interval list returns empty output.
- Sorting by end time breaks the sweep invariant.
Interview Checklist
- Sort by interval start.
- Compare current start with last merged end.
- Extend the last merged end with max end.
FAQs
Why sort first?
Sorting puts possible overlaps next to each other, so one left-to-right sweep is enough.
Why compare with the last merged interval?
After sorting, only the active last merged interval can overlap the current interval.
What is the core pattern?
Sort and sweep.