扫描线（Sweep Line）是一种将二维问题降为一维的经典思想：用一条线沿某方向扫过平面，在扫描过程中用数据结构维护当前状态，高效处理区间覆盖、面积并等问题。
一、核心思想
Mermaid · 渲染中（下方为源码）
graph TD A[事件排序] --> B[扫描线] B --> C[数据结构维护当前状态] C --> D[区间覆盖/面积并]
- 将所有事件（开始/结束）按坐标排序
- 用一条"线"从左到右（或从下到上）扫描
- 在扫描过程中维护活跃集合（通常用线段树/优先队列）
- 在每个事件点更新答案
二、矩形面积并（LeetCode 850）
思路
- 将每个矩形拆成两条竖边事件：(x, y1, y2, +1) 和 (x, y1, y2, -1)
- 按 x 排序
- 扫描时用线段树维护 y 方向的覆盖长度
- 面积 += 覆盖长度 × Δx
int rectangleArea(int[][] rectangles) {
int MOD = 1_000_000_007;
List<int[]> events = new ArrayList<>(); // {x, y1, y2, type}
Set<Integer> ySet = new TreeSet<>();
for (int[] r : rectangles) {
events.add(new int[]{r[0], r[1], r[3], 1}); // 左边 +1
events.add(new int[]{r[2], r[1], r[3], -1}); // 右边 -1
ySet.add(r[1]); ySet.add(r[3]);
}
events.sort((a, b) -> a[0] - b[0]);
int[] ys = ySet.stream().mapToInt(Integer::intValue).toArray();
int m = ys.length - 1;
int[] count = new int[m]; // 每段被覆盖次数
long area = 0;
int prevX = events.get(0)[0];
for (int[] event : events) {
int x = event[0], y1 = event[1], y2 = event[2], type = event[3];
// 累加面积
int coveredLen = 0;
for (int i = 0; i < m; i++) {
if (count[i] > 0) coveredLen += ys[i+1] - ys[i];
}
area = (area + (long)coveredLen * (x - prevX)) % MOD;
prevX = x;
// 更新覆盖
int lo = Arrays.binarySearch(ys, y1);
int hi = Arrays.binarySearch(ys, y2);
for (int i = lo; i < hi; i++) count[i] += type;
}
return (int) area;
}