title
我们给出了一个（轴对齐的）二维矩形列表 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 <= 200rectanges[i].length = 40 <= xi1, yi1, xi2, yi2 <= 109- 矩形叠加覆盖后的总面积不会超越
2^63 - 1，这意味着可以用一个 64 位有符号整数来保存面积结果。
solution
以下是压缩坐标的方法
实际上可以线性扫描 以及线段树优化，见题解。
class Solution:
def rectangleArea(self, rectangles: List[List[int]]) -> int:
xset, yset = set(), set()
for x1, y1, x2, y2 in rectangles:
xset.add(x1)
xset.add(x2)
yset.add(y1)
yset.add(y2)
# xset, yset, 是i -> x的映射
xset = sorted(xset)
yset = sorted(yset)
# xmap,ymap是x -> i的映射
xmap = {}
ymap = {}
for i, v in enumerate(xset):
xmap[v] = i
for i, v in enumerate(yset):
ymap[v] = i
n = len(xset)
grid = [[0] * len(yset) for _ in range(len(xset))]
for x1, y1, x2, y2 in rectangles:
'''
注意这里range右侧范围不是],是),这样grid[i][j]的意义就是到(i+1,j+1)的区间都是属于grid[i][j]的
grid[i][j]为1时，面积为(xset[i+1]-xset[i])*(yset[j+1]-yset[j])
'''
for i in range(xmap[x1],xmap[x2],1):
for j in range(ymap[y1],ymap[y2],1):
grid[i][j] = 1
ans = 0
mod = 10**9+7
for i, row in enumerate(grid):
for j, val in enumerate(row):
if val:
ans += (xset[i+1]-xset[i])*(yset[j+1]-yset[j])
ans %= mod
return ans