What intervals are
Your calendar app shows five meetings today — some of them overlap. How does the app merge them into tidy blocks so it can tell you when you're actually free?
That's an interval problem. Each meeting is a
[start, end] pair — a range on a timeline. Any list of ranges is a list of intervals. Interval problems ask you to merge overlapping ranges, detect collisions, or pick the largest non-overlapping subset.Here's the catch: if the intervals arrive in random order, finding overlaps means comparing every pair — that's
O(n²). Three intervals means three comparisons; a hundred means nearly five thousand. It gets expensive fast.But what if the intervals were sorted? Then overlaps could only happen between neighbours — and you'd only need a single left-to-right pass to settle everything. That one insight — sort first, then sweep once — is the key that unlocks nearly every interval problem.
2,6
1,3
8,10
Quick check
Why is checking overlaps in an unsorted list expensive?
Answer it in the interactive lesson to keep your progress.
How it works, step by step
We have a pile of possibly-overlapping ranges like
[[2,6], [1,3], [8,10]] and want the tidy, merged version. The whole trick is: sort by start, then sweep once, merging each interval into the previous block whenever they touch.The steps
- Sort the intervals by start time. Now an overlap can only happen with the interval right before — no far-apart comparisons.
- Keep a current block, starting with the first interval.
- For each next interval: if it starts before (or when) the block ends (
next.start <= block.end) → they overlap → extend the block's end tomax(block.end, next.end). - Otherwise there's a gap → the block is finished; push it and start a new block from this interval.
(Using
max in step 3 matters: a fully-contained interval like [2,4] inside [1,6] must not shrink the block.)Trace it on [[2,6], [1,3], [8,10]] (sorted first: [[1,3], [2,6], [8,10]]):
- Start block
[1,3] [2,6]: 2 ≤ 3 → overlap → end =max(3, 6)= 6 → block becomes[1,6][8,10]: 8 > 6 → gap → push[8,10]- Result:
[[1,6], [8,10]]✓
In the animation, watch the current block's right edge: an overlapping interval only ever stretches it (or leaves it alone — that is the
max at work), while a gap freezes the block and starts a new one. Before each interval arrives, predict: extend, or new block? In JavaScript, one way to write those steps (sort((a, b) => a[0] - b[0]) orders by start):This section has a step-by-step animation in the interactive lesson.
const intervals = [[2, 6], [8, 10], [1, 3]]; // out of order
intervals.sort((a, b) => a[0] - b[0]); // sort by start
console.log(intervals); // [[1,3],[2,6],[8,10]]
function merge(list) {
const sorted = [...list].sort((a, b) => a[0] - b[0]);
const out = [sorted[0]];
for (let i = 1; i < sorted.length; i++) {
const last = out[out.length - 1];
if (sorted[i][0] <= last[1]) { // overlaps → extend
last[1] = Math.max(last[1], sorted[i][1]);
} else {
out.push(sorted[i]); // gap → new block
}
}
return out;
}
console.log(merge([[2, 6], [1, 3], [8, 10]])); // [[1,6],[8,10]]Quick check
Block is [1, 6] and the next (sorted) interval is [2, 4]. Predict the block after the merge.
Answer it in the interactive lesson to keep your progress.
Where it breaks (and how not to get burned)
- Forgetting to sort. The sweep assumes sorted starts — skip the sort and you silently get wrong answers. This is the number-one interval bug.
- Touching endpoints. Do
[1,3]and[3,5]overlap? For merging, usually yes (they touch at3, so use<=). For can-attend-all, touching is fine (use strict<). Know which the problem wants — mixing up<and<=flips the answer. - Extending with the wrong end. Always use
Math.max(current.end, next.end)— a fully-contained interval like[2,4]inside[1,6]must not shrink the block. Using justnext.endwould break containment.
Quick check
[a,b] and [c,d] overlap exactly when…
Answer it in the interactive lesson to keep your progress.
Take it further — can one person attend every meeting?
The same two ideas — sort by start, then scan neighbours — solve a different classic. Given a list of meetings, can one person attend all of them? They can only if no two overlap.
This time we don't need to merge — we just need to find the first clash. Sort by start, then check: does any meeting start before the previous one ends?
Trace
[[1,3], [3,6], [8,10], [9,12]]:[3,6]starts at 3,[1,3]ends at 3 → 3 is NOT < 3 → no clash[8,10]starts at 8,[3,6]ends at 6 → 8 > 6 → no clash[9,12]starts at 9,[8,10]ends at 10 → 9 < 10 → clash! → returnfalse
Notice the subtle difference: merging uses
<= (touching counts as overlapping), but attending uses strict < (touching is fine — one meeting ends right as the next begins). Same pattern, different comparator:function canAttendAll(meetings) {
const sorted = [...meetings].sort((a, b) => a[0] - b[0]);
for (let i = 1; i < sorted.length; i++) {
if (sorted[i][0] < sorted[i - 1][1]) return false; // a clash
}
return true;
}
console.log(canAttendAll([[1, 3], [3, 6], [8, 10], [9, 12]])); // false — [8,10] & [9,12] clash
console.log(canAttendAll([[1, 3], [3, 6], [8, 10]])); // true — no clashesQuick check
Meetings [1, 3] and [3, 5]. Predict: can one person attend both, and would merging combine them?
Answer it in the interactive lesson to keep your progress.
How fast is it? (complexity)
Using the vocabulary from the Complexity & Time lesson, the cost is dominated by the sort:
| Approach | Time | Why |
|---|---|---|
| compare every pair | O(n²) | overlaps can hide anywhere |
| sort, then sweep | O(n log n) | sort dominates; the sweep itself is O(n) |
Space is
O(n) for the output list.Key takeaways:
- Almost every interval problem = sort, then sweep once comparing each interval with its neighbour.
- Overlap test: each starts before the other ends (
a[0] <= b[1] && b[0] <= a[1]); decide whether touching counts (<=vs<). - Merge: extend with
Math.max(current.end, next.end)so a contained interval can't shrink the block. - Different sort key for different problems: sort by start for merge/detect, sort by end for maximum non-overlapping subset (greedy — keep whichever finishes earliest).
The same sort-then-sweep tames any pile of ranges. These classics each get their own lesson later (no need to know them yet): insert interval (splice a new range into a sorted list), meeting rooms II (minimum rooms, via a min-heap of end times), and non-overlapping intervals (greedy removal, sorting by end time). In the closing animation, watch the two highlighted intervals as the overlap test runs — the test is symmetric (each must start before the other ends), which is why it catches partial overlap, containment, and touching alike. Next up in order: Greedy — you already used its signature move here: sort, then take what fits.
This section has a step-by-step animation in the interactive lesson.