题目描述

在一个平面内给定一些矩形，求这些矩形围成的面积是多少。

样例

Input: [[0,0,2,2],[1,0,2,3],[1,0,3,1]]
Output: 6
在纸上画一下，重叠的部分不算，可以发现是6.

算法

(扫描线) $O(n^2)$

先对x坐标排序，去重，并且离散化为x_i(x的位置，排序后为第几个x)。
接下来对于每个矩形有两个四元组{y1,x1,x2,1}和{y2,x1,x2,-1}排序。
其中下边界用1来表示，上边界用-1来表示。

我们按照y进行扫描：
每次先计算上一步中x的有效长度和当前deltay的乘积，即为当前这一轮增加的面积。
我们维护一个count数组记录在第i个x的位置下面有几个还没出边界的矩形，注意，这里是左闭右开区间。
上一步中x的有效长度可以利用count计算得出。
只要count大于0，表示当前的x下面至少是有一个底面的，那么当前轮即使是0也没有关系，表明刚好出边界，但依旧需要计算面积。

时间复杂度分析：由于在一个y位置，均需要确定当前y中x的有效长度，所以复杂度为$O(x)$ * $O(y)$ = $O(n^2)$

C++ 代码

class Solution {
public:
    int rectangleArea(vector<vector<int>>& rectangles) {
        int mod = 1e9+7;
        vector<int> xran;
        for (auto r:rectangles){
            xran.push_back(r[0]);
            xran.push_back(r[2]);

        }

        sort(xran.begin(),xran.end());
        auto iter = unique(xran.begin(),xran.end());

        xran.erase(iter,xran.end());

        unordered_map<int,int> x_i;

        for (int i = 0;i<xran.size();++i){
            x_i[xran[i]] = i;
        }

        vector<vector<int>> L;
        for (auto r:rectangles){
            int x1 = r[0],x2 = r[2];
            int y1 = r[1],y2 = r[3];
            L.push_back({y1,x1,x2,1});
            L.push_back({y2,x1,x2,-1});
        }
        sort(L.begin(),L.end());
        long long area = 0,cur_y = 0,x_sum = 0;

        vector<int> count(xran.size(),0);

        for (auto r:L){

            int y = r[0];
            int x1 = r[1],x2 = r[2],sig= r[3];
            area += (y-cur_y)*x_sum;
            area %= mod;
            cur_y = y;
            for (int i = x_i[x1]; i<x_i[x2];++i)
                count[i] += sig;

            x_sum = 0;
            for (int i = 0;i<xran.size();++i)
                if (count[i]>0)
                    x_sum += xran[i+1] - xran[i];

        }

        return area;    
    }
};