Almost every interval question reduces to a single reflex: sort the intervals by start time, then make one linear pass comparing each interval's start against the running end. Master that, plus a couple of variations for inserting and for counting overlaps, and you can handle the whole family: Merge Intervals, Insert Interval, Non-overlapping Intervals, and Meeting Rooms. The template is short. What separates a clean solve from a stumble is knowing which variation the question wants and getting the boundary conditions exactly right.
We run mock interviews all day, and intervals are one of the highest-leverage patterns to drill because the payoff generalizes. Once the sort-then-scan idea clicks, four or five distinct LeetCode problems collapse into one mental model. This guide covers the core patterns, the code, and the specific places candidates lose points.
What counts as an interval problem
An interval is a pair [start, end] representing a range: a meeting from 9 to 10, a booking, a numeric segment. Interval problems ask you to reason about how these ranges relate. There are really only four questions the interviewer can dress up:
- Merge overlapping ranges into consolidated ones (Merge Intervals, LeetCode 56).
- Insert a new range into a sorted list and merge as needed (Insert Interval, LeetCode 57).
- Remove the fewest ranges to eliminate overlap (Non-overlapping Intervals, LeetCode 435).
- Count how many ranges are active at once, or whether any two conflict (Meeting Rooms I and II, LeetCode 252 and 253).
These come up constantly. Merge Intervals in particular is a staple at large tech companies, frequently cited among the most commonly asked interview questions because it tests sorting, greedy reasoning, and careful boundary handling in one compact problem.
The unifying trick: two intervals a and b (with a starting first) overlap when a.end >= b.start. Almost the entire family is built on that one comparison.
The sort-then-scan template
Sorting is what makes overlaps adjacent. Without it you cannot guarantee that the intervals you need to compare sit next to each other, which forces you into an O(n^2) pairwise scan. Sort by start time and a single pass suffices.
Here is Merge Intervals, the canonical version:
def merge(intervals):
intervals.sort(key=lambda x: x[0]) # sort by start
merged = [intervals[0]]
for start, end in intervals[1:]:
if start <= merged[-1][1]: # overlap
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
return merged
Complexity is O(n log n) for the sort and O(n) for the scan, so the sort dominates. You cannot beat O(n log n) in the general case because you have to examine every interval relative to its neighbors, and sorting is the cheapest way to make those neighbors meaningful. This is a sorting problem wearing an interval costume, and recognizing that out loud is a small but real signal to the interviewer.
Two details that trip people up:
- Extend, do not replace. When merging, the new end is
max(merged[-1][1], end), not justend. A short interval fully contained inside a longer one ([1,9]then[2,3]) will silently shrink your result if you overwrite. - The last interval. Templates that only append inside an
elsebranch must remember to flush the final in-progress interval. The version above avoids this by mutating the last element in place, which is one reason we prefer it.
Insert Interval: the three-phase pattern
Insert Interval hands you an already-sorted, non-overlapping list and one new interval. Because the input is sorted, you skip the O(n log n) sort entirely and solve it in O(n) with a clean three-phase walk:
def insert(intervals, new):
res, i, n = [], 0, len(intervals)
# 1. intervals ending before new starts: keep as-is
while i < n and intervals[i][1] < new[0]:
res.append(intervals[i]); i += 1
# 2. intervals overlapping new: absorb them
while i < n and intervals[i][0] <= new[1]:
new[0] = min(new[0], intervals[i][0])
new[1] = max(new[1], intervals[i][1])
i += 1
res.append(new)
# 3. intervals starting after new ends: keep as-is
while i < n and i < n:
res.append(intervals[i]); i += 1
return res
The reason to learn this separately from Merge is that interviewers love the follow-up "the list is already sorted, can you do better than re-sorting?" If you reach for .sort() here, you have missed the point of the question. The three-phase structure (before, overlapping, after) is the answer they want, and it shows you noticed the precondition.
Counting overlaps without merging
Meeting Rooms flips the goal. Instead of consolidating ranges, you want to know how many overlap at the busiest moment, which equals the minimum number of rooms needed. Merging is the wrong tool here because merged intervals hide how many rooms were stacked.
Two approaches both work, and being able to compare them is a strong signal.
Heap of end times. Sort by start, then push each meeting's end onto a min-heap. Before adding a new meeting, pop every end that has already finished. The heap size at any point is the number of concurrent meetings, and its maximum is the answer. This is a natural fit for a heap or priority queue.
import heapq
def min_meeting_rooms(intervals):
intervals.sort(key=lambda x: x[0])
heap = []
for start, end in intervals:
if heap and heap[0] <= start:
heapq.heappop(heap)
heapq.heappush(heap, end)
return len(heap)
Sweep line with events. Split each interval into a +1 event at start and a -1 event at end, sort all events by time, and track a running counter. The peak counter value is the answer. This scales to "maximum concurrent" questions of any flavor and is worth having in your back pocket.
def min_meeting_rooms_sweep(intervals):
events = []
for s, e in intervals:
events.append((s, 1)); events.append((e, -1))
events.sort() # ties: -1 before +1 since -1 < 1
cur = peak = 0
for _, delta in events:
cur += delta
peak = max(peak, cur)
return peak
A subtle boundary question decides the tie-break: if a meeting ends exactly when another begins, do they conflict? Usually no, so the -1 (end) event should be processed before the +1 (start) event at the same timestamp. In the tuple sort above, -1 < 1, so this happens for free. Say this assumption out loud; interviewers frequently probe it.
Non-overlapping intervals: the greedy variant
Non-overlapping Intervals asks for the minimum number of intervals to remove so the rest do not overlap. The winning move is greedy: sort by end time, and whenever two intervals collide, drop the one that ends later because it forecloses more future room.
def erase_overlap(intervals):
intervals.sort(key=lambda x: x[1]) # sort by END
prev_end, removed = float('-inf'), 0
for s, e in intervals:
if s >= prev_end:
prev_end = e
else:
removed += 1 # drop the later-ending one
return removed
Note the sort key changed from start to end. This is the one interval problem where sorting by end is clearly correct, and it is the same underlying logic as the classic activity-selection problem. Candidates who memorize "always sort by start" get this one wrong, which is exactly why interviewers like it.
The broader lesson: sorting is the setup, but the sort key and the greedy choice depend on the objective. Merge wants start; interval scheduling wants end. This same "sort, then make a greedy pass" shape shows up beyond intervals in problems like Maximum Number of Consecutive Values You Can Make, where sorting the input first is what unlocks the linear greedy argument.
Where candidates lose points
From watching these solves repeatedly, the failures cluster:
| Mistake | Fix |
|---|---|
| Forgetting to sort | State it first; the scan is only valid on sorted data |
< vs <= on overlap | Decide whether touching endpoints ([1,2], [2,3]) count, and say so |
| Overwriting the merged end | Use max(cur_end, new_end) |
| Dropping the final interval | Flush after the loop, or mutate in place |
| Re-sorting an already-sorted input | Use the three-phase insert instead |
| Wrong sort key | Sort by end for scheduling, by start for merging |
The meta-skill is narrating the overlap condition and the endpoint convention before you write code. Interval bugs are almost always off-by-one errors at the boundary, and stating your assumptions turns a silent bug into a shared decision.
If you want to drill these against realistic follow-ups, practice with an AI interviewer that pushes on exactly these boundary cases rather than letting a green test suite paper over them.
FAQ
How do I know if a problem is really an interval problem?
Look for input shaped like pairs of [start, end], or anything describing ranges over a line: time slots, numeric segments, bookings, or positions. If the question involves overlaps, merging, scheduling, or "how many at once," treat it as an interval problem and reach for sort-then-scan first.
Should I always sort by start time?
No, and this is the most common trap. Sort by start for merging and inserting. Sort by end when you are selecting the maximum number of non-overlapping intervals or removing the fewest to eliminate conflicts. The objective determines the key, so pick it deliberately.
Do touching intervals like [1,2] and [2,3] overlap?
It depends on the problem, which is why you should ask or state your assumption. For merging, endpoints that touch are usually merged (<=). For meeting rooms, a meeting ending at 2 and another starting at 2 typically do not conflict. Getting this convention wrong is a classic off-by-one failure.
What is the sweep line technique and when do I use it?
Sweep line turns each interval into a start event (+1) and end event (-1), sorts all events by time, and sweeps a counter across them. Use it whenever you need the maximum number of concurrent intervals or need to process many overlapping ranges as a timeline. It generalizes past scheduling to any "active count over time" question.
How many interval problems should I practice before an interview?
Cover one of each type: Merge Intervals, Insert Interval, Non-overlapping Intervals, and Meeting Rooms II. That is roughly four problems, and together they exercise every variation of the pattern. Once you can solve all four cold and explain the sort-key choice for each, you are prepared for most interval questions you will see.