Merge Intervals¶
Also known as: Interval Merging, Overlapping Intervals, Sweep on Intervals
Sort the intervals, then walk them once, keeping a "current" interval open and either extending it (if the next one overlaps) or closing it and starting a new one. Almost every interval problem is this same loop with a different closing condition.
Before you start¶
- Comfortable sorting arrays and comparing pairs of values in your language.
What 'solved properly' looks like
Target: O(n log n) — the sort dominates. If your solution is slower than that, you've found a solution but not this pattern — the judge says "Accepted" either way, so treat this as your real benchmark.
The idea¶
You sort all intervals by their start time, then walk through them in order. You keep one "active" interval. If the next interval's start falls within the active one, you extend the active interval's end to cover it. If it doesn't, you close the active interval, record it, and start a new one. That's the entire pattern — the variation between problems is just what "overlap" means and what you do with each closed interval.
Why it matters: Scheduling, calendars, resource allocation, and range-merging problems appear constantly in real systems, and they all reduce to this single loop. Learning it once means you never need to improvise an interval handler again.
When to reach for it¶
Reach for it whenever you see intervals, ranges, or [start, end] pairs. Words like "merge", "overlap", "conflict", "meeting schedules", "minimum number of arrows" or "minimum number of rooms" are strong tells that this is the pattern.
When not to use it
The sort key is the whole game and it changes with the question — sort by start to merge, but by end for the greedy "maximum non-overlapping" family. Getting this backwards produces a plausible-looking wrong answer. Also decide explicitly whether touching intervals ([1,2] and [2,3]) count as overlapping; the problem statement will tell you, and it's a classic silent failure.
Practice set¶
Work these top to bottom. The time-box is a cue to pause and re-read the triggers above if you're still stuck when it passes — not a deadline to race. Getting unstuck by stepping back is the skill being trained.
| # | Problem | Where | Difficulty | Time-box | Role |
|---|---|---|---|---|---|
| 1 | Summary Ranges | LeetCode | Easy | 15 mins | teaching |
| 2 | Merge Intervals | LeetCode | Medium | 25 mins | teaching |
| 3 | Insert Interval | LeetCode | Medium | 25 mins | consolidation |
| 4 | Non-overlapping Intervals | LeetCode | Medium | 25 mins | consolidation |
| 5 | Minimum Number of Arrows to Burst Balloons | LeetCode | Medium | 30 mins | challenge |
Already know this? Test out.
If you can solve Minimum Number of Arrows to Burst Balloons cleanly in one sitting — handling the greedy sort-by-end logic — you already own this pattern, so move on to the next one. If it tangles you up, that's your signal to work the set from the top instead of skipping.
← Binary Search · Fast & Slow Pointers → Back to the roadmap