Overview
Interval problems describe ranges — meetings, bookings, balloons on a number line — and ask how they overlap. Two intervals [a, b] and [c, d] overlap exactly when a ≤ d and c ≤ b. Once intervals are sorted by start, any overlap must be with the most recently kept interval, so a single linear pass can merge them.
A second family is about counting overlaps at each point in time. The sweep-line technique turns each interval into two events (+1 at the start, −1 at the end), sorts the events and walks through them keeping a running count. The peak count is the number of rooms, platforms or machines needed.
Key concepts
Tick a concept once you can explain it in your own words without notes.
Complexity cheat sheet
| Operation | Cost |
|---|---|
| Sort intervals | O(n log n) |
| Merge after sorting | O(n) |
| Sweep line over 2n events | O(n log n) |
Patterns to recognise
Merge
Use it for: Merge intervals, insert interval, summary ranges.
Sort by start; extend the last interval or start a new one.
Greedy by end time
Use it for: Non-overlapping intervals, minimum arrows to burst balloons.
Sort by end; take an interval whenever it starts after the last chosen end.
Two-list intersection
Use it for: Interval list intersections.
Two pointers, one per list; advance the one that ends first.
Code template
def merge(intervals):
intervals.sort(key=lambda iv: iv[0])
merged = []
for start, end in intervals:
if merged and start <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], end) # overlap: extend
else:
merged.append([start, end])
return merged
vector<vector<int>> merge(vector<vector<int>> intervals) {
sort(intervals.begin(), intervals.end());
vector<vector<int>> merged;
for (auto& iv : intervals) {
if (!merged.empty() && iv[0] <= merged.back()[1])
merged.back()[1] = max(merged.back()[1], iv[1]); // overlap: extend
else
merged.push_back(iv);
}
return merged;
}
Common mistakes
- Whether [1, 2] and [2, 3] overlap depends on the problem — read it carefully.
- When extending, take max(end, current end); a later interval can be fully contained in the previous one.
- In sweep lines, decide whether an end event at time t is processed before a start event at t.
Quick check
Three questions on Intervals. Get all three right to earn +15 XP.
-
What is the first step in merging overlapping intervals?
Once sorted by start, each interval can only overlap the one most recently merged.
-
Intervals [a, b] and [c, d] with a <= c overlap when:
The second starts before, or exactly when, the first ends.
-
To keep the maximum number of non-overlapping intervals, the greedy choice is to always pick the one that:
Finishing early leaves the most room for the intervals that follow.
Challenges
Ordered from easiest to hardest. Solve them on LeetCode, then tick them off here. Know every concept and solve 3 to clear the level.
- Summary RangesLeetCode Easy +20
- Merge IntervalsLeetCode Medium +40
- Insert IntervalLeetCode Medium +40
- Non-overlapping IntervalsLeetCode Medium +40
- Minimum Number of Arrows to Burst BalloonsLeetCode Medium +40
- Interval List IntersectionsLeetCode Medium +40
- Minimum Interval to Include Each QueryLeetCode Hard +70
Stuck on Intervals?Ask Orbi for a hint, a fresh explanation or a review of your code.
Ask the tutor