Interval Algorithms (Merge, Meeting Rooms & Sweep)
Interval algorithms solve overlapping range problems—such as merging intervals, minimum meeting rooms, and interval intersections—in O(n log n) by sorting endpoints and sweeping linearly.
Difficulty: Medium · Interactive Visualizer · C++ / Python / Java / JS Code
Interval Algorithms (Merge, Meeting Rooms & Sweep)
Interval problems are among the highest-frequency interview and systems patterns. Almost every interval problem reduces to one of three $O(n \log n)$ templates:
1. Sort by start ascending → Merging overlapping intervals (Merge Intervals).
2. Sort by end ascending → Picking maximum non-overlapping intervals (Activity Selection).
3. Event Sweep (+1 at start, -1 at end) or Min-Heap of End Times → Counting maximum simultaneous overlaps (Meeting Rooms II).
At a Glance
| Problem | Sort Key | Complexity |
| :--- | :--- | :---: |
| Merge Overlapping Intervals | start ascending | $O(n \log n)$ |
| Max Simultaneous Intervals (Meeting Rooms II) | Events (time, ±1) or min-heap of end | $O(n \log n)$ |
| Max Non-Overlapping Intervals | end ascending | $O(n \log n)$ |
---
Practice Problems
Easy
1. Merge Overlapping Intervals (LeetCode 56)
Merge all overlapping intervals [l, r] into disjoint sorted intervals.
Approach: Sort by l ascending; if cur.l <= out.back().r, extend out.back().r = max(out.back().r, cur.r); else push cur. Time: $O(n \log n)$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
std::vector<std::pair<int, int>> mergeIntervals(std::vector<std::pair<int, int>> ivs) {
std::sort(ivs.begin(), ivs.end());
std::vector<std::pair<int, int>> res;
for (const auto& iv : ivs) {
if (res.empty() || iv.first > res.back().second) res.push_back(iv);
else res.back().second = std::max(res.back().second, iv.second);
}
return res;
}
int main() {
for (const auto& [l, r] : mergeIntervals({{1, 3}, {2, 6}, {8, 10}, {15, 18}}))
std::cout << "[" << l << "," << r << "] ";
std::cout << "\n";
return 0;
}
</details>
Intermediate
2. Minimum Meeting Rooms Required (LeetCode 253)
Given meeting intervals [start, end), find the minimum number of conference rooms needed simultaneously.
Approach: Create sweep events (start, +1) and (end, -1) (with -1 sorted before +1 at ties so back-to-back meetings reuse the same room!) and track the maximum running sum. Time: $O(n \log n)$.
<details>
<summary>Show C++ Solution</summary>
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
int minMeetingRooms(const std::vector<std::pair<int, int>>& meetings) {
std::vector<std::pair<int, int>> events;
events.reserve(meetings.size() * 2);
for (const auto& [s, e] : meetings) {
events.push_back({s, 1});
events.push_back({e, -1});
}
std::sort(events.begin(), events.end()); // (-1) sorts before (+1) at equal time!
int active = 0, peak = 0;
for (const auto& [t, delta] : events) {
active += delta;
peak = std::max(peak, active);
}
return peak;
}
int main() {
std::cout << minMeetingRooms({{0, 30}, {5, 10}, {15, 20}}) << "\n"; // 2
return 0;
}
</details>
---
Related Algorithms
- Activity Selection — maximize non-overlapping intervals.
- Sweep Line — 2D geometric generalization of interval event sweeps.