Week 10 — Intervals: The Sort-Then-Sweep Toolkit

Phase: Month 02 — Patterns · Week: 10 of 24 · Theme: Intervals Problems: 5 (p46–p50) — 3 Medium + 1 Medium + 1 Hard Prereqs: Sorting, heap (Week 9), two-pointer mindset, comparator-by-key

Why Intervals

Almost every “calendar / scheduling / resource allocation / range” question reduces to one of three primitives:

1. Merge — combine overlapping ranges into a smaller set.
2. Sweep / chronological scan — process start and end events in time order.
3. Active-count tracking — at any time t, how many intervals cover t?

Once you see the connection, problems that look wildly different (calendar bookings, CPU scheduling, free-time computation, conflict detection, lane assignment) collapse into one of two algorithms:

• Sort by start time → linear sweep, or
• Sort start-events + end-events independently → two-pointer or min-heap sweep.

The interview signal isn’t “did you solve this problem”; it’s “can you SEE this as an interval problem and pick the right primitive immediately.” Week 10 builds that pattern recognition.

Mental Models to Cement

1. Two intervals [a, b] and [c, d] overlap iff a ≤ d AND c ≤ b (or equivalently max(a, c) ≤ min(b, d)). For half-open [a, b), replace ≤ with <. ASK the interviewer about endpoint semantics.

2. Sort by start, sweep: after sorting, you only need to compare each interval with the LAST appended interval in your result. O(n log n) sort dominates; sweep is O(n).

3. Two-pointer over starts and ends: sort starts and ends INDEPENDENTLY; sweep both with two pointers; when starts[i] < ends[j], a meeting begins (active++), else one ends (j++, active–). Peak active is the answer (LC 253 Meeting Rooms II).

4. Min-heap of end-times: sort by start; for each interval, if heap top ends ≤ current start, reuse that room (pop); push current end. Heap size = peak rooms. O(n log n).

5. Sweep line / event list: create (start, +1) and (end, -1) events; sort (with ties: -1 before +1 for half-open semantics, +1 before -1 for closed); accumulate prefix sum to track active count.

6. Greedy “earliest-ending-first” for maximum non-overlapping subset (LC 435): sort by END time, take any interval whose start ≥ previous end. Classic activity-selection.

7. Insert into sorted list of disjoint intervals (LC 57): three phases — copy strictly-before, merge overlapping, copy strictly-after. No need to re-sort.

8. Endpoint conventions are footguns. [1, 2] and [2, 3] — overlap or not? In calendars, usually not ([start, end) half-open: meeting ending at 2 doesn’t conflict with one starting at 2). In LC 56, they DO merge (closed intervals). ASK.

9. Comparator by first key: intervals.sort(key=lambda x: x[0]) is the idiom. Python sorts tuples elementwise, so intervals.sort() works when shape is [start, end]. Don’t write a custom comparator unless tie-breaking on the second key matters.

10. Off-by-one on merge: the merged interval’s end is max(prev_end, cur_end), NOT cur_end. Easy bug when intervals are fully contained inside larger ones.

Problem Lineup

Daily Schedule (5 days @ 90 min)

Saturday: 30-min mock with p49 or p50. Sunday: Re-solve any problem you took > 25 min on; write the comparator and feasibility on a blank page from memory.

Anti-Patterns to Notice This Week

• Sort by both start AND end as a “safety” comparator — adds nothing for merge (start-only suffices); confuses activity-selection (must be end).
• For Meeting Rooms II: maintain a sorted list of meetings and insert one by one — O(n²).
• For Insert Interval: append + re-sort + run merge — works but O(n log n) when O(n) is possible.
• Treat [1,2] and [2,3] as always overlapping (or always not) — depends on convention; ASK.
• For Employee Free Time: flatten without sorting per-employee structure — loses information that each employee’s intervals are pre-sorted; you can heap-merge in O(N log K) instead of O(N log N).

Readiness Checklist

By Sunday, you should:

• Recognize an interval problem from its phrasing in < 60 seconds.
• Decide instantly: “merge → sort-by-start”, “max non-overlap → sort-by-end”, “peak active → heap or two-pointer”, “invert → sweep”.
• Implement Merge Intervals in ≤ 8 minutes without lookup.
• Articulate the half-open vs closed endpoint trade-off.
• Reproduce the Meeting Rooms II heap solution on a blank page in ≤ 12 minutes.
• Sketch the two-pointer alternative to Meeting Rooms II.
• Explain why activity-selection sorts by END, not by START (exchange argument).

Looking Ahead

Week 11 (planned): Monotonic Stack — Daily Temperatures, Next Greater Element I/II, Largest Rectangle in Histogram, Trapping Rain Water deep-dive, Sliding Window Maximum. Intervals → monotonic stack is a natural progression: both are “sweep with auxiliary structure”; monotonic stack adds the discipline of maintaining sorted order in the auxiliary structure during the sweep.