Micro-questions over the intervals pattern. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. Why it exists
1. What does the naive pairwise check cost?
Answer
— for each interval, compare against all later ones. 500,000 checks for 1,000 intervals.
2. What does sorting by start time buy?
Answer
You can process in order and merge as you go — the first interval sets the initial block, and each subsequent one either extends it or starts a new one.
3. What does the pattern turn into?
Answer
— the sort dominates; the merge itself is linear.
B. The overlap condition
4. When do [a,b] and [c,d] overlap, once sorted by start?
Answer
When b >= c — the first interval has not ended before the second begins.
5. Do [1,3] and [3,5] overlap?
Answer
In most problem definitions, yes — which is why the check is start <= last_end, not <. Check the specific problem; this is a common off-by-one trap.
6. Why must you compare against the last merged interval and not the previous input one?
Answer
After a merge, the effective end time may have grown past what the original list showed.
C. The merge
7. Write the loop.
Answer
intervals.sort(key=lambda p: p[0])
merged = [intervals[0]]
for start, end in intervals[1:]:
last_start, last_end = merged[-1]
if start <= last_end:
merged[-1] = [last_start, max(last_end, end)]
else:
merged.append([start, end])8. Why max(last_end, end) rather than just end?
Answer
The new interval may be entirely contained within the merged one — e.g. [1,10] then [2,3] — in which case taking end would shrink the block.
9. Trace [[1,3],[2,6],[8,10],[15,18]].
Answer
[1,3] → [2,6] overlaps (2 ≤ 3) → [1,6] → [8,10] does not (8 > 6) → new block → [15,18] does not → new block. Result [[1,6],[8,10],[15,18]].
D. Variants
10. Meeting Rooms II — what is the algorithm?
Answer
Sort starts and ends separately. Sweep the starts: if the next start is before the current earliest end, you need another room; otherwise advance the end pointer.
11. Why does that work?
Answer
It counts the peak number of simultaneously active intervals, which is exactly the number of rooms needed.
12. Employee free time — how do you build it?
Answer
Flatten all schedules, merge them, then take the gaps between consecutive merged intervals.
13. Minimum removals to make non-overlapping — what changes?
Answer
You sort by END time, not start — this is the same greedy as interval scheduling, keeping the interval that finishes earliest.
14. State the sorting rule across variants.
Answer
Different problems need different sort keys: merging needs start time, minimum removals needs end time. Getting the key wrong is the defining bug of this pattern.
E. Costs
15. What is the complexity, and what dominates?
Answer
, dominated by the sort; the merge pass is .
16. What other patterns share this shape?
Answer
Most patterns needing sorted input first — modified binary search, and the sorting-based greedy algorithms.
17. Summarise the pattern in one sentence.
Answer
Sort by the right endpoint for the question being asked, then sweep once comparing each interval only against the running block.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Overlapping Intervals — the pattern
- Selection & Scheduling — Question Bank — where the sort key is proved
Software engineering
Infrastructure & security
Computer science
Hardware & engineering