Interval Merge Pattern
Sort intervals by start time, then iterate and merge overlapping intervals by extending the end of the current interval when the next interval's start ≤ current end.
Interval merge = stacking TV show recordings on a timeline. Sort by start time, then swallow any show that overlaps with the current block. Two shows overlap if one starts before the other ends.
Sort by start: O(n log n). Merge pass: O(n). Total O(n log n). Two intervals [a,b] and [c,d] overlap if c ≤ b (c starts before b ends). Merge to [a, max(b,d)]. Common variations: insert interval (binary search for insertion point, merge with neighbors), non-overlapping intervals (greedy: keep interval with smallest end to maximize room for others — equivalent to activity selection), meeting rooms (count max overlapping intervals at any point).
Meeting rooms II (minimum meeting rooms): use a min-heap of end times. Sort by start time. For each meeting, if the earliest-ending meeting is already done (heap top ≤ current start), reuse that room. Otherwise add a new room. Heap size at end = minimum rooms needed. O(n log n). Equivalent to: sweep line on start/end events, count concurrent events. Interval DP: dp[i][j] = min cost to solve the subproblem on interval [i,j] — used for matrix chain multiplication, burst balloons, stone merge. The state space is O(n²) and transitions are O(n) → total O(n³).
Interval problems almost always start with sorting by start time. Once sorted, the merge pass is a single O(n) scan. For insert interval, I binary search for the right position and then merge with adjacent overlaps. For minimum meeting rooms, I switch to a heap of end times — greedily reuse the room that frees up soonest. The key invariant to check is whether overlap is strict (c < b) or non-strict (c <= b) — it depends on whether [1,3] and [3,5] are considered overlapping in the problem.
Forgetting to sort intervals before merging makes the algorithm incorrect — the merge assumes intervals are in order. Also: the merge condition is c ≤ current_end (not c < current_end) for non-strict overlap. If two intervals share only a boundary point (e.g., [1,3] and [3,5]) and the problem says they should NOT be merged, use strict inequality c < b.