AntInLoop

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