扫描线

850. 矩形面积 II

我们给出了一个（轴对齐的）二维矩形列表 rectangles 。 对于 rectangle[i] = [x1, y1, x2, y2]，其中（x1，y1）是矩形 i 左下角的坐标， (xi1, yi1) 是该矩形 左下角 的坐标， (xi2, yi2) 是该矩形 右上角 的坐标。
计算平面中所有 rectangles 所覆盖的 总面积 。任何被两个或多个矩形覆盖的区域应只计算 一次 。
返回 总面积 。因为答案可能太大，返回 109 + 7 的 模 。

示例 1：

输入：rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]] 输出：6 解释：如图所示，三个矩形覆盖了总面积为6的区域。 从(1,1)到(2,2)，绿色矩形和红色矩形重叠。 从(1,0)到(2,3)，三个矩形都重叠。
示例 2：
输入：rectangles = [[0,0,1000000000,1000000000]] 输出：49 解释：答案是 1018 对 (109 + 7) 取模的结果， 即 49 。

提示：

• 1 <= rectangles.length <= 200
• rectanges[i].length = 4
• 0 <= xi1, yi1, xi2, yi2 <= 109
• 矩形叠加覆盖后的总面积不会超越 2^63 - 1 ，这意味着可以用一个 64 位有符号整数来保存面积结果。

思路：按x轴分段考虑
时间复杂度：O(n2logn)

class Solution {
    public int rectangleArea(int[][] rectangles) {
        int n = rectangles.length;
        int[] a = new int[2 * n];
        for (int i = 0; i < n; i ++) {
            a[i] = rectangles[i][0];
            a[i + n] = rectangles[i][2];
        }
        Arrays.sort(a);
        long res = 0;
        for (int i = 1; i < 2 * n; i++) {
            res += calc(rectangles, a[i - 1], a[i]);
        }
        return (int)(res % 1000000007);
    }
    long calc(int[][] r, int x, int y) {
        List<int[]> t = new ArrayList<>();
        for (int[] p : r) {
            if (p[0] <= x && p[2] >= y) {
                t.add(new int[]{p[1], p[3]});
            }
        }
        Collections.sort(t, (o1, o2) -> (o1[0] - o2[0]));
        long s = 0;
        int ll = -1, rr = -1;
        for (int[] p : t) {
            if (p[0] <= rr) {
                rr = Math.max(rr, p[1]);
            } else {
                s += 1L * (rr - ll) * (y - x);
                ll = p[0];
                rr = p[1];
            }
        }
        s += 1L * (rr - ll) * (y - x);
        return s;
    }
}