0850. Rectangle Area II

题目信息

题号:

0850

难度:

Hard

主题:

几何、矩形并集、面积

原题:

LeetCode 0850

重点:

求所有轴对齐矩形覆盖区域的并集面积,重叠部分只能计算一次;最终结果对 10^9+7 取模

题目重述

给定若干与坐标轴平行的矩形,rectangles[i] = [x1, y1, x2, y2] 表示左下角 (x1, y1) 和右上角 (x2, y2),并保证每个矩形宽、高均为正。

请计算至少被一个矩形覆盖的平面区域总面积。多个矩形的重叠部分只能计入一次,边界本身没有面积。由于结果可能很大,返回面积对 10^9 + 7 取模后的值。

1 <= rectangles.length <= 200,每项恰好包含四个坐标;所有坐标在 [0, 10^9] 范围内,每个矩形面积非零。

自建示例

两个矩形部分重叠:

输入:rectangles = [[0,0,2,2],[1,1,3,3]]
输出:7
解释:两个矩形面积各为 4,交叠的 1×1 区域面积为 1,因此并集面积为 4 + 4 - 1 = 7。

只有一个单位矩形:

输入:rectangles = [[5,7,6,8]]
输出:1
解释:矩形数量达到题目允许的最小值,唯一矩形宽和高都为 1,没有重叠需要去重,因此并集面积为 1。