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
- Interval Algorithms — 1D event-sweep foundation.
- Line Segment Intersection — paired with Sweep Line in Bentley–Ottmann.