Almost every interval problem reduces to one move: sort by start time, then run a single linear sweep that merges overlaps, counts concurrency, or greedily keeps the interval with the earliest end. Learn the overlap test and the three canonical sweep shapes and you have the whole category.
Sort the intervals by start, and the chaos of “which of these n bars overlap which?” collapses into a single left-to-right sweep where the only question you ever ask is “does this one touch the onerunning boundary on my left?” — cur.start <= prev.end. That single comparison is the entire category.
Stop picturing an array of [start, end] pairs. Picture horizontal bars laid on a time axis. Unsorted, they're a tangle — any bar might overlap any other, so checking all pairs is O(n²). The instant you sort by start, the bars line up so that each one can only ever touch the bars immediately to its left. You drag one vertical “sweep line” from left to right and process each bar exactly once.
Because of the sort, you never have to remember all the bars behind you — only one running boundary: the right edge of the interval (or group) you are currently building. Everything reduces to comparing the next bar's left edge to that single boundary.
Here is the same set of intervals before and after sorting by start. After sorting, the left edges only ever move rightward as you walk down — that monotonicity is what makes the single-boundary sweep correct:
unsorted (chaos — overlaps hide everywhere):
[---------] [3,9]
[----] [1,4]
[-----] [10,14]
[--------] [6,12]
──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──►
1 2 3 4 5 6 7 8 9 10 11 12 13 14
sorted by start — now each bar can only touch its NEIGHBORS:
[----] [1,4]
[---------] [3,9]
[--------] [6,12]
[-----] [10,14]
──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──┼──►
1 2 3 4 5 6 7 8 9 10 11 12 13 14Now run the sweep. Keep one running bar; for each next bar, the overlap test decides whether to stretch the run or close it:
running interval = the bar we are currently extending. walk left to right; ask only: cur.start <= run.end ? run [----] run = [1,4] cur [---------] 3 <= 4 → OVERLAP → end=max(4,9)=9 run [-----------] run = [1,9] cur [--------] 6 <= 9 → OVERLAP → end=max(9,12)=12 run [--------------] run = [1,12] cur [--] 10<=12 → OVERLAP → end=max(12,14)=14 run [-----------------] run = [1,14] (all four → one) a GAP (cur.start > run.end) is the only thing that closes a run and opens a fresh one.
Everything in this category is built from one fact. Two closed intervals [a,b] and [c,d] overlap iff a <= d and c <= b. Once you've sorted by start so the earlier-starting interval is on the left, a <= d is automatic, and the test shrinks to a single inequality:
cur.start <= prev.end. True ⇒ they touch (merge / count them together). False ⇒ a gap (close the group, start fresh).That's the only primitive you need. “Merge intervals,” “can attend all meetings,” “insert interval,” “non-overlapping intervals” — each is this comparison wrapped in a slightly different bookkeeping loop. The only nuance is whether touching endpoints count: use <= for closed intervals (merge), < when touching is allowed (attend-all-meetings).
Faced with a list of [start, end] pairs, climb these rungs in order — the code falls out at the bottom:
run.end (merge) or lastEnd (greedy). Apply the overlap test to each next interval; stretch, count, or skip accordingly.+1 / -1 events (or a min-heap of end times) and track the peak live count.The whole pattern said as one invariant you can mutter before coding: “Sort by start. Keep one running interval. For each next interval, if its start is ≤ my running end, it overlaps — extend; otherwise it's a gap — emit and reset.” The plain-English skeleton below is the entire merge family:
sort intervals by start # the universal first move
run = intervals[0] # the ONE boundary we compare to
for cur in intervals[1:]:
if cur.start <= run.end: # THE overlap test (whole vocab)
run.end = max(run.end, cur.end) # MERGE: stretch run
else: # a gap
emit(run) # close the run ...
run = cur # ... and open a fresh one
emit(run) # never forget the last runThe onlythings that change between problems are the sort key (start vs. end), what “emit” does (push a merged bar, increment a counter, count a removal), and whether the overlap test uses <= or <. The shape never changes.
“Minimum meeting rooms” / “max overlap” breaks the single-boundary trick: at any instant several intervals can be live, so one running end can't represent them. The fix is to stop thinking about intervals and think about events: every start is a +1 (a room opens), every end is a -1 (a room frees). Sort all events by time and sweep — the answer is the peak of the running counter:
meetings: [0,30] [5,10] [15,20]
events on the timeline (+1 opens a room, -1 frees one):
time : 0 5 10 15 20 30
evt : +1 +1 -1 +1 -1 -1
live : 1 2 1 2 1 0
▲ ▲
two meetings live at once → need 2 rooms
answer = the PEAK of the live counter = 2.
(equivalently: a min-heap of end times; its size is the live count.)The two-sorted-arrays version (one sorted starts[], one sorted ends[], two pointers) and the min-heap-of-end-times version are the same idea: a min-heap's size is the live count, and popping an expired end is exactly processing a -1 event.
Almost every wrong interval answer traces back to the wrong sort key. The two keys answer two different questions:
SORT BY START SORT BY END
(merge / insert / count) (max non-overlapping kept)
[----] [--]
[-----] ← extend the run [---] ← keep earliest-end first,
[--] or count live [-----] leaves the most room
[--]
"who do I touch on my left?" "which can I greedily keep?"start ≤ end → stretch the run) or doesn't (gap → close the run, open a new one). The Visualize tab shows the running bar growing and snapping shut on the time axis.Raw intervals arrive in arbitrary order. Sorting by start time gives you a critical guarantee: when you process interval i, every interval that could overlap it from the left has already been handled. That transforms an O(n²) pairwise comparison problem into a single left-to-right sweep.
a = [a0, a1] and b = [b0, b1] (with a0 <= b0 after sorting) overlap when b0 <= a1. Equivalently, they are disjoint when b0 > a1.Whether touching endpoints like [1,2],[2,3]count as overlapping depends on the problem statement — read it carefully. Most LeetCode problems treat them as overlapping (closed intervals), but "can attend all meetings" treats them as non-overlapping (open-ended).
Once sorted, every interval question is one of three shapes — each with a specific sweep strategy:
lastEnd; extend it on overlap, push a new interval on gap. Used in "merge intervals" and "insert interval."O(n log n).The sort is the bottleneck — the sweep itself is O(n). For the sweep-line / min-heap variant (counting rooms) the heap push/pop adds a log n factor per event, still O(n log n) total.
The "minimum meeting rooms" / "max concurrent intervals" problem has an elegant sweep-line solution that avoids a heap:
starts[] and ends[].starts left to right with pointer s; advance end pointer e whenever a room frees up (starts[s] >= ends[e]).rooms counter equals the number of active intervals at any moment; track its maximum.[1,3] [2,6] [8,10] [15,18]. Open a running interval on the first one. Sort, then sweep the overlaps.Reach for the intervals playbook whenever the input is a list of [start, end] pairs and the question involves overlaps, merging, scheduling, or counting simultaneous events. The sort-by-start invariant is almost always the unlock.
| "merge overlapping intervals" / "combine intervals" | sort by start, sweep and extend lastEnd on overlap |
| "insert into a sorted list of non-overlapping intervals" | three-phase insert: before / merge overlaps / after |
| "min meeting rooms" / "max concurrent events" | sweep-line (sorted starts + ends, two pointers) or min-heap of end times |
| "can attend all meetings?" / "are all intervals non-overlapping?" | sort by start, check any adjacent pair overlaps |
| "remove the fewest intervals to make non-overlapping" | sort by end, greedy keep earliest-end, count removals |
| "schedule tasks by deadline" / "activity selection" | classic greedy: sort by end time, keep non-overlapping greedily |
| "for each query find the smallest/largest interval containing it" | offline: sort queries + intervals, sweep with a min-heap keyed by interval size |
When → Any problem asking you to combine overlapping intervals into the minimal set of disjoint intervals. The output is a new list; input need not be sorted.
function merge(intervals: number[][]): number[][] {
// Universal first move: sort by start time
intervals.sort((a, b) => a[0] - b[0]);
const out: number[][] = [intervals[0]];
for (let i = 1; i < intervals.length; i++) {
const last = out[out.length - 1];
const cur = intervals[i];
if (cur[0] <= last[1]) {
// Overlap — extend the running interval's end if needed
last[1] = Math.max(last[1], cur[1]);
} else {
// Gap — start a fresh interval
out.push(cur);
}
}
return out;
}last reference (as above), it's already in out — but in some implementations you must push it after the loop.When → The input is already sorted and non-overlapping; you insert one new interval and return the updated sorted non-overlapping list. The three phases eliminate the need to re-sort.
function insert(intervals: number[][], newInterval: number[]): number[][] {
const out: number[][] = [];
let i = 0, [s, e] = newInterval;
const n = intervals.length;
// Phase 1 — strictly before: intervals that end before newInterval starts
while (i < n && intervals[i][1] < s) out.push(intervals[i++]);
// Phase 2 — overlapping: merge everything that touches newInterval
while (i < n && intervals[i][0] <= e) {
s = Math.min(s, intervals[i][0]);
e = Math.max(e, intervals[i][1]);
i++;
}
out.push([s, e]); // push the merged result
// Phase 3 — strictly after: remainder
while (i < n) out.push(intervals[i++]);
return out;
}intervals[i][1] < s (interval strictly before), phase 2 ends when intervals[i][0] > e (interval strictly after). The middle phase merges everything that touches.When → Count the maximum number of simultaneously active intervals (min rooms, min platforms, max overlap). Prefer this over a heap when you only need the count, not the assignment.
function minMeetingRooms(intervals: number[][]): number {
const n = intervals.length;
const starts = intervals.map(v => v[0]).sort((a, b) => a - b);
const ends = intervals.map(v => v[1]).sort((a, b) => a - b);
let rooms = 0, maxRooms = 0, e = 0;
for (let s = 0; s < n; s++) {
if (starts[s] < ends[e]) {
// New meeting starts before the earliest-ending meeting finishes
rooms++;
} else {
// A room freed up — reuse it
e++;
}
maxRooms = Math.max(maxRooms, rooms);
}
return maxRooms;
}starts[s] < ends[e] means a new meeting starts before the earliest-ending one finishes — a new room is needed. Otherwise that room frees up, so advance e.When → Maximize the number of non-overlapping intervals kept (equivalently, minimize removals). Sort by end time — this is the activity-selection greedy.
function eraseOverlapIntervals(intervals: number[][]): number {
// Greedy: keep the interval with the earliest end time to leave maximum room
intervals.sort((a, b) => a[1] - b[1]); // sort by END (not start!)
let kept = 0, lastEnd = -Infinity;
for (const [s, e] of intervals) {
if (s >= lastEnd) {
// No overlap with the last kept interval — keep this one
lastEnd = e;
kept++;
}
// Otherwise skip (remove) it — counted implicitly
}
return intervals.length - kept; // number removed
}Merge/insert/meeting-rooms problems sort by start; the greedy non-overlapping problem sorts by end. Mixing them up produces subtly wrong answers that pass many test cases. Always ask: "Am I maximising kept intervals (→ sort by end) or sweeping left-to-right for merges (→ sort by start)?"
For closed intervals [1,2] and [2,3], the overlap test b[0] <= a[1] returns true— they share the point 2. Most LeetCode merge/insert problems treat this as an overlap. But "can attend all meetings" (#252) asks if you can attend both, so [1,2],[2,3] is fine (the first ends exactly when the second begins). Read the constraint before coding the test.
In "merge intervals" it's tempting to extend intervals[i] in place while using ias the loop variable. This corrupts the data you're still reading. Always write into a separate output array (or a mutable last reference into the output array).
Some merge implementations accumulate a "current" interval outside the output array and only push it when a gap is detected. If the last group of intervals all overlap, the loop ends without a gap — the final accumulated interval is never pushed. Add a out.push(current) after the loop, or use the out[out.length - 1] reference pattern shown above which keeps the running interval inside out from the start.
out[last][1] on overlap, push a fresh entry on gap. Classic application of the merge template.#435Non-overlapping Intervals#435 · Medium. Sort by endtime, greedily keep any interval whose start is >= the last kept end. Answer is n − kept. Classic activity-selection.#252Meeting Rooms#252 · Easy. Sort by start, then check every adjacent pair: if intervals[i][0] < intervals[i-1][1] return false. One pass, O(1) extra space.#253Meeting Rooms II#253 · Medium. Two approaches: (1) sweep-line — sort starts and ends separately, two-pointer scan; (2) min-heap of active end times — for each meeting start, pop the heap if the earliest-ending room is free, then push the current end. Both are O(n log n).#1851Minimum Interval to Include Each Query#1851 · Hard. Offline approach: sort both queries and intervals by value / start. Sweep through intervals with a min-heap keyed by interval size (end − start + 1); for each query, add all intervals whose start <= query, evict those whose end < query, then the heap top is the smallest containing interval.