Explore interval interview patterns on an animated timeline: insert and merge intervals, meeting rooms and interval queries. Sort, sweep and study Python solutions.
The pattern
Intervals: sort them, then sweep
Interval problems are about ranges on a line: meetings, bookings, segments. The trick is nearly always the same: sort (usually by start), then make one pass, comparing each interval only with the last one you kept, or sweeping through start and end events.
1Sort by start first
Once intervals are sorted by start, any overlap is between neighbours: an interval can only overlap the last one you kept. Almost every interval problem begins with this sort.
2Overlap means: each starts before the other ends
Two intervals [a, b] and [c, d] overlap exactly when a < d and c < b (or ≤, if touching counts). Check the problem: in some, [1,2] and [2,3] overlap; in others they don't.
3Sweep through events
For “how many at once”, only the moments intervals start and end matter. Sort those events and sweep: +1 at a start, −1 at an end. The peak is the number of rooms needed.
How to spot which sweep
- Merge or insert: sort by start, extend the last kept interval.
- Fewest removals / most kept: keep the interval that ends earliest.
- How many at once: sweep sorted start and end times (or a heap of end times).
- Many queries: sort the queries too and sweep both together.
Reading the pictures
- Each interval is a bar on its own lane, against a shared number line along the top.
- Teal is the interval being read; green is in the result; red is removed or clashing; faded is absorbed or done.
- A vertical line marks the moment or query point being processed.
NeetCode 150 · Intervals
All 6 problems
Pick a problem to see it solved step by step. They're in NeetCode's order, roughly easiest first.
Insert Interval
MediumBlind 75Given sorted, non-overlapping intervals and a new interval, insert it so the list stays sorted and non-overlapping (merging where needed).
intervals = [[1,2], [3,5], [6,7], [8,10], [12,16]], newInterval = [4,8]
intervals (top), the one being inserted, and the result (bottom)
variables
- new interval so far
- [4,8]
Press Play or Step to watch the solution run.
Brute force vs the pattern
On this input:
- Pattern: O(n)
- 5 ops
- Brute force
- 38 ops
On a bigger input (200 intervals):
- Pattern
- 103 ops
- Brute force
- 3,277 ops
Append the new interval, sort everything again and merge: O(n log n), ignoring that the list was already sorted. (The sort is estimated as n·log₂n comparisons plus as many moves.)
“ops” is an illustrative count of selected algorithm operations, with estimates for sorting. It excludes drawing and frame creation and is not a timing benchmark. The complexity describes the Python solution. On small inputs a brute-force search may find the answer sooner.
How it works: Insert Interval
Step by step
- Interval being compared
- The new interval (growing)
- In the result
- Absorbed
Press Start or Step: the step the animation is on lights up below.
- 1
Walk the sorted intervals
res = [] - 2
Ends before the new one starts → copy
elif newInterval[0] > intervals[i][1]: res.append(intervals[i]) - 3
Overlaps → absorb it
else: newInterval = [min(...starts), max(...ends)] - 4
Starts after it ends → add new, then the rest
if newInterval[1] < intervals[i][0]: res.append(newInterval); return res + intervals[i:] - 5
The result
res.append(newInterval); return res
The list is already sorted, so one pass is enough. Each interval is either entirely before the new one (copy it), overlapping it (absorb it: the new interval's start becomes the smaller start, its end the larger end), or entirely after it.
The first interval entirely after means the new interval is final: add it, then everything that's left, unchanged.
Spot it in an interview
- Sorted intervals and one change: a single pass with three cases (before, overlap, after).
- Two intervals overlap when each starts before the other ends.
One pass; the result has at most n + 1 intervals.
Credits
Learn more from NeetCode
The problem list and order come from the NeetCode 150 by NeetCode (neetcode.io). The solutions here follow the approaches NeetCode teaches in the linked videos; the animations, explanations and code were written for CodeQuest. If these help, NeetCode's videos and site are well worth your time.
Problem statements are summarised in our own words; the full versions are on LeetCode.