📏 Intervals
Interval problems involve ranges [start, end]. The key insight: sort by start time, then handle overlaps greedily. Most problems reduce to merge, insert, or count operations.
Core Patterns
| Pattern | Approach | Example |
|---|---|---|
| Merge overlapping | Sort by start, merge when curr.start ≤ prev.end |
Merge Intervals |
| Insert & merge | Find position, expand new interval to cover overlaps | Insert Interval |
| Count non-overlapping | Sort by end, greedily keep non-overlapping | Activity selection |
| Interval intersection | Two-pointer on sorted lists, advance smaller end | Interval List Intersections |
| Min interval for queries | Sort both, use min-heap keyed by interval size | Query coverage |
Templates
// Merge Intervals — sort by start, then merge
sort(intervals.begin(), intervals.end());
vector<vector<int>> res;
for (auto& iv : intervals) {
if (res.empty() || iv[0] > res.back()[1])
res.push_back(iv);
else
res.back()[1] = max(res.back()[1], iv[1]);
}
// Insert Interval — three-phase scan
vector<vector<int>> res;
int i = 0, n = intervals.size();
// Phase 1: intervals entirely before newInterval
while (i < n && intervals[i][1] < newInterval[0])
res.push_back(intervals[i++]);
// Phase 2: merge overlapping
while (i < n && intervals[i][0] <= newInterval[1]) {
newInterval[0] = min(newInterval[0], intervals[i][0]);
newInterval[1] = max(newInterval[1], intervals[i][1]);
i++;
}
res.push_back(newInterval);
// Phase 3: intervals entirely after
while (i < n) res.push_back(intervals[i++]);
Overlap Condition
Two intervals [a, b] and [c, d] overlap iff a ≤ d && c ≤ b.
They do not overlap iff b < c (first ends before second starts) or d < a.
Complexity
| Pattern | Time | Space |
|---|---|---|
| Merge / Insert | O(n log n) | O(n) |
| Intersection (two sorted lists) | O(m + n) | O(m + n) |