[!info] related notes 算法面试题型 MOC 堆常见题

Max Overlapping Segments (Sweep Line + Heap)

本例采用非空半开区间 [start, end)，要求 start < end，求同时覆盖同一点的最大区间数。端点相接的 [1, 2) 与 [2, 3) 不算重合；这是下方 end <= start 弹出规则的前提。若题目采用闭区间且端点也算重合，应改为 end < start。

思路

• 按 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) -> Integer.compare(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;
    }
}

示例原地重排 segs 的行顺序，未校验反向或零长度区间。空输入返回 0；堆最坏 O(n) 空间。比较器使用 Integer.compare，避免端点相减溢出。

Related

• 堆常见题