AntInLoop

Sweep Line Algorithm

The Sweep Line paradigm slides an imaginary vertical line across sorted geometric events, maintaining active objects in a balanced BST or Segment Tree to solve rectangle union area, skyline, and segment intersections in O(n log n).

Difficulty: Hard · Interactive Visualizer · C++ / Python / Java / JS Code

Sweep Line Algorithm

The Sweep Line algorithm reduces 2D geometric problems into a 1D sequence of sorted events (start/end x-coordinates). Imagine sweeping a vertical line from $x = -\infty$ to $x = +\infty$: the set of active objects only changes at discrete event points, and maintaining the active set in a balanced BST (std::multiset) or Segment Tree solves Skyline, Area of Union of Rectangles, and Segment Intersections in $O(n \log n)$ time!

Practice Problems

Hard

1. The Skyline Problem (LeetCode 218)

Given buildings [left, right, height], output the key points (x, y) tracing the outer skyline silhouette in $O(n \log n)$ time.

Approach: Create two events per building: (left, -height) (enter; negative sorts taller entrances first!) and (right, +height) (leave; positive sorts shorter exits first!). Maintain active heights in a std::multiset<int> initialized with {0} and emit a key point whenever *heights.rbegin() changes! Time: $O(n \log n)$.

<details>

<summary>Show C++ Solution</summary>

#include <algorithm>
#include <iostream>
#include <set>
#include <tuple>
#include <utility>
#include <vector>

std::vector<std::pair<int, int>> getSkyline(const std::vector<std::tuple<int, int, int>>& buildings) {
    std::vector<std::pair<int, int>> events;
    for (const auto& [l, r, h] : buildings) {
        events.push_back({l, -h});
        events.push_back({r, h});
    }
    std::sort(events.begin(), events.end());

    std::multiset<int> heights = {0};
    int prevMax = 0;
    std::vector<std::pair<int, int>> res;
    for (const auto& [x, h] : events) {
        if (h < 0) heights.insert(-h);
        else heights.erase(heights.find(h));
        int curMax = *heights.rbegin();
        if (curMax != prevMax) {
            res.push_back({x, curMax});
            prevMax = curMax;
        }
    }
    return res;
}

int main() {
    auto sky = getSkyline({{2, 9, 10}, {3, 7, 15}, {5, 12, 12}});
    for (const auto& [x, y] : sky) std::cout << "(" << x << "," << y << ") ";
    std::cout << "\n"; // (2,10) (3,15) (7,12) (12,0)
    return 0;
}

</details>

---

Related Algorithms