1Understand
The idea
Sort intervals by start (or by end, when choosing how many to keep), then sweep from left to right. Two neighbours overlap when the next one starts before the current one ends, so merging, inserting and counting overlaps become a single pass. For "how many at once", sort the start and end events separately.
Intuition
Sort intervals by start (or by end when selecting how many to keep), then sweep left to right. Two neighbours overlap when the next starts before the current ends, merging, inserting and conflict counts become one pass.
For "how many overlap at once". Treat starts and ends as separate events, sort them, and sweep a counter. Sorting by end is the classic activity-selection greedy.
Draw the intervals on a line; the sweep is just reading that picture left to right.
What you will be able to do
- Define overlap precisely (touching?)
- Use a heap or sweep line for concurrent counts
When to use it
- Merge overlapping ranges
- Meeting rooms
- Minimum removals to avoid overlap
2See it
Walkthrough
Merge overlapping intervals
[[1,3],[2,6],[8,10]], sort, then extend or append.
1 / 6
Sort by start. merged starts empty.
Live template
Line 1 active
Complexity: time O(n log n), space O(n)
O(n log n) from sorting, then O(n). Pairwise checks are O(n²). Sweep-line event sorting is the right tool when the question is occupancy over time, not just merge.
Read the walkthrough as text
Merge intervals. [[1,3],[2,6],[8,10],[15,18]].
- Sort by start (already sorted).
- Seed result with
[1,3]. Next[2,6]overlaps (2 ≤ 3) → extend end to6. [8,10]does not overlap → append. Same for[15,18].- Result
[[1,6],[8,10],[15,18]].
Meeting-rooms II: sort start and end arrays; increment on start, decrement on end, track peak count.
3Recognise it
Kinds of problems (10)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
Merge intervals
Example. Merge all overlapping intervals.
How. Sort by start; extend last end if overlap else append new interval.
Insert an interval
Example. Insert new interval into sorted non-overlapping list.
How. One pass: append before, merge middle overlaps, append rest.
Non-overlapping intervals (min removals)
Example. Fewest intervals to remove so none overlap.
How. Sort by end; keep interval if start ≥ last end (activity selection).
Meeting rooms (max concurrency)
Example. Maximum simultaneous meetings.
How. Sort starts and ends; sweep with two pointers counting active.
Interval intersections of two lists
Example. All overlaps between two interval lists.
How. Two pointers: advance list with earlier end; record max(starts) to min(ends).
Sweep line over start and end events
Example. Count online users or overlap depth.
How. Events +1 at start, −1 at end; sort and prefix max.
Answer queries with the smallest covering interval
Example. Shortest interval containing at least k listed points.
How. Sort by start; slide end while coverage count ≥ k.
Sort by start, then by end descending (covered intervals)
Example. Count covered intervals, parent contains child.
How. Sort start asc, end desc; stack or sweep to drop dominated intervals.
Keep disjoint intervals in a sorted structure
Example. My Calendar I/II, insert if no triple overlap.
How. Sorted list or tree map of intervals; binary search neighbours for overlap.
Skyline (sweep line with a heap)
Example. Building skyline silhouette.
How. Sort events; heap of active heights; on end remove lazy or multiset height.
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
Touching intervals
Why it happens. [1,2] and [2,3] overlap or not depending on who you ask.
How it fails. Merge treats touching as overlap but removal counts as overlap, inconsistent answer.
Fix. Read statement: merge often uses s <= last_end; non-overlap may require s > last_end.
End not maximised
Why it happens. Overwrite merged end with new interval’s end looks like “latest finish”.
How it fails. Merge [1,5] with [2,3] → [1,3] shrinks cover, should be [1,5].
Fix. On overlap: merged[-1][1] = max(merged[-1][1], e).
Not sorted first
Why it happens. One pass scanning in input order feels like a sweep.
How it fails. Later interval [0,1] after [3,4] never merges with earlier middle overlap.
Fix. Sort by start (or end per problem) before linear scan.
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.