扫描线算法

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;
}

List<List<Integer>> getSkyline(int[][] buildings) {
    List<int[]> events = new ArrayList<>();
    for (int[] b : buildings) {
        events.add(new int[]{b[0], -b[2]}); // 进入（负高度）
        events.add(new int[]{b[1], b[2]});  // 离开
    }
    events.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);

    TreeMap<Integer, Integer> heights = new TreeMap<>();
    heights.put(0, 1);
    List<List<Integer>> result = new ArrayList<>();
    int prevMax = 0;

    for (int[] e : events) {
        int h = Math.abs(e[1]);
        if (e[1] < 0) { // 进入
            heights.merge(h, 1, Integer::sum);
        } else { // 离开
            if (heights.get(h) == 1) heights.remove(h);
            else heights.merge(h, -1, Integer::sum);
        }
        int curMax = heights.lastKey();
        if (curMax != prevMax) {
            result.add(List.of(e[0], curMax));
            prevMax = curMax;
        }
    }
    return result;
}