#创作挑战赛#
3妹
3妹：2哥，台风梅花今天夜里要登陆上海了，今天下午已经登陆浙江了。2哥：是啊，风力14级，还是很强的，你看现在都下大雨刮大风了。3妹：据说将是1950年以来登陆上海的最大台风。2哥：恩，下这么大的雨，晚上就不出去吃饭了，还要关好门窗。3妹：那晚饭吃什么，吃红烧牛肉的还是香菇炖鸡的？2哥：还是给我来个老坛酸菜的吧。3妹：切，时间还早，我先刷道算法题再吃。2哥：那我也来一道算法题当开胃菜。
讲课
题目：我们给出了一个（轴对齐的）二维矩形列表 rectangles 。 对于 rectangle[i] = [x1, y1, x2, y2]，其中（x1，y1）是矩形 i 左下角的坐标， (xi1, yi1) 是该矩形 左下角 的坐标， (xi2, yi2) 是该矩形 右上角 的坐标。
计算平面中所有 rectangles 所覆盖的 总面积 。任何被两个或多个矩形覆盖的区域应只计算 一次 。
返回 总面积 。因为答案可能太大，返回 109 7 的 模 。
示例 1：
image.png
输入：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 <= 200rectanges[i].length = 40 <= xi1, yi1, xi2, yi2 <= 109矩形叠加覆盖后的总面积不会超越 2^63 - 1 ，这意味着可以用一个 64 位有符号整数来保存面积结果。
java代码：
class Solution {
public int rectangleArea(int[][] rectangles) {
int N = rectangles.length;
Set<Integer> Xvals = new HashSet();
Set<Integer> Yvals = new HashSet();
for (int[] rec: rectangles) {
Xvals.add(rec[0]);
Xvals.add(rec[2]);
Yvals.add(rec[1]);
Yvals.add(rec[3]);
}
Integer[] imapx = Xvals.toArray(new Integer[0]);
Arrays.sort(imapx);
Integer[] imapy = Yvals.toArray(new Integer[0]);
Arrays.sort(imapy);
Map<Integer, Integer> mapx = new HashMap();
Map<Integer, Integer> mapy = new HashMap();
for (int i = 0; i < imapx.length; i)
mapx.put(imapx[i], i);
for (int i = 0; i < imapy.length; i)
mapy.put(imapy[i], i);
boolean[][] grid = new boolean[imapx.length][imapy.length];
for (int[] rec: rectangles)
for (int x = mapx.get(rec[0]); x < mapx.get(rec[2]); x)
for (int y = mapy.get(rec[1]); y < mapy.get(rec[3]); y)
grid[x][y] = true;
long ans = 0;
for (int x = 0; x < grid.length; x)
for (int y = 0; y < grid[0].length; y)
if (grid[x][y])
ans = (long) (imapx[x 1] - imapx[x]) * (imapy[y 1] - imapy[y]);
ans %= 1_000_000_007;
return (int) ans;
}
}
,
