Intervals
The "intervals" family of problems works with lists of [start, end] pairs — meeting times, time spans, number ranges. The foundational step is almost always sorting by start point.
After sorting, an interval can only overlap the one just before it in the result, so a single sweep is enough to merge or insert. The easy mistakes are how you define "overlapping" at the boundary (< or <=) and updating the end to the maximum of the two ends.
Like scheduling meetings in a single room — each meeting is an interval [start, end].
- Sort by start time, then sweep from left to right: if a new interval overlaps the previous one, merge them; if it does not, start a new one.
- Sorting first is the key that lets you compare only against the adjacent interval.
How to spot it
When you see these cues in the problem, reach for Intervals
| Keyword in the problem | Why it points to this topic |
|---|---|
| list of [start, end] | Sort by start before scanning |
| merge overlapping | New end = max(current end, candidate end) |
| schedule / rooms / resources | Count concurrently overlapping intervals |
When to use
4 typical situations where this topic applies
Merge overlapping intervals (merge intervals)
Insert a new interval into a sorted list
Count the rooms / resources needed so nothing overlaps
Find intersections / free gaps between intervals
When NOT to use
3 situations where this topic doesn't fit — know them so you don't overuse them
Only 1–2 isolated intervals: handling the cases directly is faster than a general algorithm
Intervals change constantly (dynamic insert / delete): consider an Interval Tree / Segment Tree
Choosing intervals to optimize by weight (weighted scheduling): that is a different DP / Greedy problem
Illustration
A diagram of how this topic works.
Sort by start, then merge when the next interval overlaps the previous one. [1,3] and [2,6] overlap → [1,6]; [8,10] is separate, so it stays.
Code template
Most problems in this topic share this scaffold — copy it, then fill in the problem-specific logic.
function intervalPattern(intervals: number[][]): number[][] {
// 1. Sort by start point
intervals.sort((a, b) => a[0] - b[0])
const result: number[][] = []
for (const [start, end] of intervals) {
const last = result[result.length - 1]
if (last && start <= last[1]) {
last[1] = Math.max(last[1], end) // overlap → merge
} else {
result.push([start, end]) // no overlap → new interval
}
}
return result
}Recap
A quick summary — reread it before your interview
Key points
Most problems start with a sort by start: O(n log n)
Two intervals a, b overlap when a.start <= b.end and b.start <= a.end
When merging: new end = max(current end, end of the interval being examined)
Common mistakes
Forgetting to sort before sweeping → misses overlaps between intervals that are far apart
Wrong overlap condition (mixing up < and <=) for intervals that touch at the boundary
Setting the end to the new interval's end instead of the max of the two ends
Complexity
Sắp xếp O(n log n) rồi quét 1 lần O(n)Practice problems for this topic
Grouped by difficulty — work through them in order to build confidence