Max Overlapping Segments (Sweep Line + Heap)
扫描线：按起点排序 + 小根堆维护当前覆盖的线段终点。
#resource / algorithm
#type / howto
#status / growing
#ds / heap
#algo / sweep-line
[!info] related notes 算法面试题型 MOC 堆常见题
Max Overlapping Segments (Sweep Line + Heap)
给定若干线段 [start, end]，求同一时刻最多有多少条线段重合。
思路
- 按
start从小到大排序。 - 用小根堆存当前“活跃线段”的
end。 - 扫描每条线段：
- 把堆里所有
end <= start的线段弹出（它们已经不再覆盖当前 start）。 - 把当前线段的
end入堆。 - 堆大小就是当前重合数，维护最大值。
- 把堆里所有
复杂度：O(n log n)（排序 + 堆操作）。
Java Template
import java.util.*;
public class MaxOverlap {
public static int maxOverlap(int[][] segs) {
Arrays.sort(segs, (a, b) -> a[0] - b[0]);
PriorityQueue<Integer> heap = new PriorityQueue<>();
int ans = 0;
for (int[] s : segs) {
int start = s[0], end = s[1];
while (!heap.isEmpty() && heap.peek() <= start) heap.poll();
heap.add(end);
ans = Math.max(ans, heap.size());
}
return ans;
}
}