Sort by start, then sweep: merging, inserting, and detecting overlaps in interval lists.
What the intervals pattern is
Interval problems hand you ranges [start, end] - meetings, bookings, segments - and ask about their relationships: merge the overlapping ones, count conflicts, find gaps, intersect two schedules. Unsorted, every pair might interact: O(n^2) checks. Sorted by start, all interaction becomes local: each interval can only overlap the one 'current' merged block, and a single left-to-right sweep settles everything.
Two facts do all the work. The overlap test: a.start <= b.end and b.start <= a.end (equivalently max(starts) <= min(ends)). And the sort-key rule of thumb: sort by START to merge or build timelines; sort by END to select a maximum set of compatible intervals (that variant lives in the greedy pattern).
How to recognize it
The input contains pairs meaning ranges over a line (time, positions), and the ask involves overlap, merging, gaps, coverage, or 'can these coexist'. Meeting-rooms questions, calendar bookings, balloon bursting, employee free time - all of it is this pattern in different clothes.
Also recognize the resource-counting variant: 'how many rooms/platforms are needed' is the maximum number of simultaneously open intervals - solved by sweeping start and end events separately or with a min-heap of end times.
The merge sweep template
Sort by start. Keep the last merged interval as the current block. For each next interval: if it starts after the block ends, the block is finished - emit it and start a new one; otherwise it overlaps (or touches), so extend the block's end with max(). The max() matters: a short interval nested inside a long one must not shrink the block.
pseudocode
sort intervals by start
merged = [first interval]
for (start, end) in rest:
if start > merged.last.end: # disjoint: new block
merged.append((start, end))
else: # overlap: extend
merged.last.end = max(merged.last.end, end)
return merged
Complexity
O(n log n) for the sort dominates; the sweep is O(n) and O(1) beyond the output. Already-sorted input (as in insert-interval) drops the whole thing to O(n) - noticing and saying that is free credit. The heap-based room-counting variant is O(n log n) with O(n) heap in the worst case.
Common pitfalls
Extending with `end = new_end` instead of `end = max(end, new_end)` - a nested interval silently truncates the merged block.
Boundary semantics: does [1,3] overlap [3,5]? Touching endpoints usually merge (>= / <=), but conflict-counting problems often treat them as compatible. Ask, decide, and keep the comparison consistent.
Sorting by end when the task is merging (or by start when the task is selecting a maximum compatible set) - the two classic tasks want different keys.
Comparing every pair out of reflex - if you wrote a nested loop over intervals, the sort was missed.
In two-list intersection, advancing the wrong pointer: always advance the interval that ends first, since nothing else can still intersect it.
Worked examples
1. Merge intervalsmedium
Given a list of intervals, merge all overlapping ones and return the disjoint result.
Sort by start so any interval overlapping the current block is adjacent to it in processing order - interaction becomes purely local.
Walk the list holding one open block. Next interval starts within the block (start <= block.end): extend with max of ends. Starts after: close the block, open a new one.
The max() guard handles nesting: merging [1,10] with [2,3] must keep end 10.
Emit the final block after the loop. O(n log n) total; the sweep itself is one pass.
pseudocode
sort intervals by start
result = [intervals[0]]
for (s, e) in intervals[1:]:
if s <= result.last.end:
result.last.end = max(result.last.end, e)
else:
result.append((s, e))
return result
Remember: Sorting by start makes overlap adjacent - one open block and a max() on the end merges everything in a single pass.
2. Insert intervalmedium
Given non-overlapping intervals sorted by start and a new interval, insert it and merge as needed.
Input is already sorted - re-sorting throws away the O(n) opportunity. Process in three phases instead.
Phase 1: intervals ending before the new one starts pass through untouched.
Phase 2: every interval overlapping the new one gets absorbed - widen the new interval with min(starts) and max(ends) until intervals start after it ends.
Phase 3: append the widened interval, then the untouched remainder. One pass, O(n), no sort.
pseudocode
result = []
i = 0
while i < n and intervals[i].end < new.start: # before
result.append(intervals[i]); i += 1
while i < n and intervals[i].start <= new.end: # overlapping
new.start = min(new.start, intervals[i].start)
new.end = max(new.end, intervals[i].end)
i += 1
result.append(new)
while i < n: # after
result.append(intervals[i]); i += 1
return result
Remember: Sorted input splits cleanly into before / overlapping / after - absorb the middle into the new interval and stitch the three phases together.
3. Interval list intersectionsmedium
Given two lists of disjoint sorted intervals, return the intersections of every pair that overlaps.
Two sorted lists, pairwise interaction - a two-pointer sweep, one pointer per list.
The candidate intersection of the current pair is [max(starts), min(ends)]; it is real when that range is non-empty (max <= min).
Advance the pointer of the interval that ends first: it can intersect nothing further, while the longer one might overlap the other list's next interval.
O(n + m) time, output-sized space. The advance rule is the whole insight - it is the same 'discard the exhausted side' logic as merging.
pseudocode
i = 0, j = 0; result = []
while i < len(A) and j < len(B):
lo = max(A[i].start, B[j].start)
hi = min(A[i].end, B[j].end)
if lo <= hi: result.append((lo, hi))
if A[i].end < B[j].end: i += 1
else: j += 1
return result
Remember: Intersection is [max of starts, min of ends] when non-empty - and always retire the interval that ends first.
Check yourself
Try to answer before revealing - retrieving from memory is what makes it stick.
1What is the standard test for whether intervals a and b overlap?
a.start == b.start
✓ a.start <= b.end and b.start <= a.end
a.end - a.start > b.end - b.start
abs(a.start - b.start) < a.end
Each must start before (or as) the other ends - equivalently max(starts) <= min(ends). Whether equality counts as overlap is a boundary-semantics decision to fix per problem.
2Why sort by start before merging?
Because output must be sorted
✓ So every interval that can overlap the current merged block is processed adjacent to it, making one linear sweep sufficient
Sorting by end also works identically
To enable binary search
Start-order guarantees no later interval can begin before the current block does, so overlap with anything other than the open block is impossible - global pairwise checking collapses to a local test.
3In the merge sweep, why extend with max(current.end, new.end)?
It is equivalent to using new.end
✓ An interval nested inside the block would otherwise shrink the block's end and break subsequent merges
To handle negative numbers
To keep the result sorted by end
Sorting by start says nothing about ends: merging [1,10] then [2,3] must keep 10. Plain assignment truncates the block and falsely splits later overlaps - the pattern's most common bug.
4In two-list intersection, after emitting a candidate intersection, which pointer advances?
Both pointers
✓ The one whose interval ends first - it cannot intersect anything else
The one whose interval started first
Alternate between the lists
The earlier-ending interval is exhausted: every future interval on the other list starts even later. The longer interval stays live because it may span several intervals on the opposite list.
Frequently asked questions
When do I sort by start versus by end?
Start for constructing things - merging, timelines, insertion. End for selecting a maximum set of non-conflicting intervals (activity selection), where earliest-finish is the provably safe greedy pick. Mispicking the key is the most common interval mistake.
How are 'minimum meeting rooms' style questions solved?
Count maximum simultaneous overlap: either split into start/end event arrays, sort both, and sweep with a counter, or sweep start-sorted intervals against a min-heap of active end times - the heap's peak size is the room count. Both are O(n log n).
Do touching intervals like [1,3] and [3,5] overlap?
It depends on the problem's semantics: merging usually treats touching as mergeable (use <=), while conflict detection often treats them as compatible (a meeting can start when another ends). State the convention before coding and keep every comparison consistent with it.