Synthesis: which pattern to use?
Four interval patterns covered. Since the section is lean, the decision tree is too — but the reflex of sorting by the right endpoint is what separates those who solve from those who get stuck.
The section's decision tree
1. Need to MERGE overlapping intervals in an arbitrary list?
→ sort by START + scan, merging into the last in the result
2. The list is ALREADY sorted and I'm going to INSERT an interval?
→ three phases (before / merge / after), in O(n) without sorting
3. "Minimum to remove" / "maximum that fits without conflict"?
→ GREEDY: sort by END, keep the one that finishes earliest
4. "How many resources/rooms at the same time?" / "maximum overlap"?
→ EVENT SWEEP (+1 at the start, −1 at the end) or min-heap of the ends
The question that guides everything: sort by start or by end? Start to merge/insert (process in line order); end for greedy choices (the one that frees space earliest).
The full map of the section
| Pattern | Key question | Sort by | Time |
|---|---|---|---|
| Merge | "merge the overlapping ones" | start | O(n log n) |
| Insert | "insert into a sorted list" | (already sorted) | O(n) |
| Greedy | "minimum to remove / maximum that fits" | end | O(n log n) |
| Event sweep | "how many at the same time / rooms" | start and end | O(n log n) |
Note: almost everything is O(n log n) dominated by the sort — except insert, which exploits the already-sorted list and drops to O(n). The scan itself is always linear; the creativity lies in which endpoint to sort by and what to accumulate (last interval? counter of active ones?).
Section quiz
Statements you haven't seen in the lessons. Identify the pattern and the reason why. 6+ correct: ready for the exam.
🧠 Section quiz: Intervals
0/61. 'Given a schedule, what is the MAXIMUM number of meetings that fit without overlapping?' Which pattern?
2. 'Merge overlapping intervals' and 'insert into an already-sorted set': why do the complexities differ?
3. 'What is the point in time with the most overlapping intervals?' Which technique?
4. 'Minimum number of arrows to burst balloons (intervals on the x-axis)' uses which pattern?
5. 'Combine two ALREADY-sorted lists of intervals, returning the intersections.' Which approach?
6. What is the decision that guides almost all interval problems?
Ready for the exam?
The final exam of the Intervals section has three brand-new problems — easy, medium, and hard — with hidden cases. The hard one (Car Pooling) applies the event sweep in a new scenario (passengers getting on and off): exactly the meeting-rooms reasoning. The four lessons cover everything you need.
Good luck on the exam! Go back to the section page and click "Final exam."