问题描述：

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

核心思路：

• 该题是扫描线题目。【扫描线题目其实就是一类区间问题，如官方题解所讲解的那样，扫描线就是一种离散化的技巧，将大范围的连续的坐标转化成离散的坐标】
• 暴力解法其实不难理解。
  • 矩形面积其实就是宽和高，固定宽，进而求每一个不重叠的高。
  • 具体来说，把一个矩形范围视作两个行和两个列（离散化）。
  • 首先，行与行之间的距离就是宽，宽是固定的。
  • 接着，再处理列与列的重叠关系，因为本题数据量较低，暴力法可以直接搜索所有矩形，选出当前宽所囊括的所有矩形，把这些矩形的两个列作为区间存入一个临时数组中，之后把临时数组排序（也就是把区间排序），最后就遍历区间找出所有范围即可，也就是找出当前宽下所有的矩形高。【这里处理列就是扫描线问题，扫描线问题可以用前缀数组来处理】
• 优化算法就是用线段树处理扫描线部分。【等整理了线段树再重写一下该题】
• 该题难度不算特别大，考察的东西都比较直接，是扫描线的模板题。

代码实现：

• 暴力解法代码实现如下：【逻辑来自下面参考内容中的链接】

  class Solution
  {
  public:int rectangleArea(vector<vector<int>>& rectangles){int MOD = 1e9+7;// 行的处理，用于求宽vector<int> vec; // 行数组for(auto& rect : rectangles) // 把 x1 和 x2 存入数组中vec.emplace_back(rect[0]), vec.emplace_back(rect[2]);sort(vec.begin(), vec.end());// 列的处理，用于求高，高的处理就是扫描线的处理long long ans = 0;for(int i = 1; i < vec.size(); ++i){int a = vec[i-1], b = vec[i];int len = b - a; // 宽if(len == 0) continue;vector<vector<int>> tmp;for(auto& rect : rectangles) // 列的区间if(rect[0] <= a and b <= rect[2]) tmp.push_back({rect[1], rect[3]});sort(tmp.begin(), tmp.end(), [&](const vector<int>& a, const vector<int>& b){return a[0] == b[0] ? a[1] < b[1] : a[0] < b[0];});long long cnt = 0, l = -1, r = -1; // 前一个区间for(auto& cur : tmp){if(cur[0] > r) // 没有重叠{cnt += r - l;l = cur[0], r = cur[1];}else if(cur[1] > r) // 重叠，更新区间的右边界r = cur[1];}cnt += r - l;ans += cnt * len;ans %= MOD;}return (int)ans;}
  };
  

参考内容：

• 【宫水三叶】扫描线模板题