Intervals
Sort intervals by start, then sweep linearly. Merge, intersect, count overlaps, and detect meeting-room collisions all fall out of a single linear pass. A min-heap of end times adds resource-allocation flavors on top.
Interval problems reduce to 'sort by start, then linear sweep'. The sweep maintains a 'current' interval and decides per next-interval: merge (overlap), push (gap), or absorb (covered). When resource contention enters (room allocation, parallel scheduling), a min-heap of end times tracks active intervals and decides reuse-or-allocate per new arrival.
The difference-array trick is a cousin: instead of materializing intervals, encode each `[l, r)` as `delta[l] += x; delta[r] -= x` and prefix-sum to recover.
When to reach for this pattern
- Input is `[start, end]` pairs
- Detect overlapping or covered intervals
- Merge intervals, count overlaps, find gaps in a schedule
- Resource allocation (rooms, machines, channels)
- Two interval lists — find intersection / union
Canonical template
// merge
sort(intervals.begin(), intervals.end());
vector<vector<int>> ans;
for (auto& it : intervals) {
if (!ans.empty() && it[0] <= ans.back()[1])
ans.back()[1] = max(ans.back()[1], it[1]);
else
ans.push_back(it);
}
// minimum rooms (heap of end times)
sort(intervals.begin(), intervals.end());
priority_queue<int, vector<int>, greater<int>> pq;
for (auto& it : intervals) {
if (!pq.empty() && pq.top() <= it[0]) pq.pop();
pq.push(it[1]);
}
return pq.size();C++ · adapt the names and types to your problem.
Common pitfalls
- Inclusive vs exclusive endpoints:
[1, 2]and[2, 3]may or may not overlap by convention - Sorting by end vs by start — different problems need different keys
- Difference-array off-by-one for inclusive ranges:
delta[end + 1] -= x - Forgetting
max(end)on merge when the next interval is fully inside the current
Related patterns
Problems (11)
- Medium
- Medium
- Medium
- Medium
- Hard
- Medium
- Medium
- Medium
- Medium
- Hard
- Hard