0850：矩形面积 II（2235 分）

2018-06-10 约 539 字预计阅读 2 分钟次阅读

力扣第 88 场周赛第 4 题

题目

给你一个轴对齐的二维数组 rectangles 。对于 rectangle[i] = [x1, y1, x2, y2]，其中（x1，y1）是矩形 i 左下角的坐标， (x_i1, y_i1) 是该矩形 左下角 的坐标， (x_i2, y_i2) 是该矩形 右上角 的坐标。

计算平面中所有 rectangles 所覆盖的 总面积 。任何被两个或多个矩形覆盖的区域应只计算一次。

返回 总面积 。因为答案可能太大，返回 10⁹ + 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
解释：答案是 10¹⁸ 对 (10⁹ + 7) 取模的结果， 即 49 。

提示：

1 <= rectangles.length <= 200
rectanges[i].length = 4
0 <= x_i1, y_i1, x_i2, y_i2 <= 10⁹

分析

有点类似 0218，不过遍历坐标 x 时，要维护的不是高度集合，而是区间集合。

每一轮根据当前横坐标 cur_x 、上一轮横坐标 prev_x，上一轮区间集合覆盖的长度 prev_h，即可计算出 cur_x 和 prev_x 之间覆盖的面积。然后更新 prev_x 和 prev_h 即可。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


def rectangleArea(self, rectangles: List[List[int]]) -> int:
    def cal(A):
        res, end = 0, 0
        for s, e in A:
            res += max(end, e) - max(s, end)
            end = max(end, e)
        return res

    from sortedcontainers import SortedList
    d = defaultdict(list)
    for x1, y1, x2, y2 in rectangles:
        d[x1].append((y1, y2, 1))
        d[x2].append((y1, y2, 0))
    res, mod = 0, 10**9+7
    H, prev_x, prev_h = SortedList(), 0, 0
    for x in sorted(d):
        res = (res+(x-prev_x)*prev_h)%mod
        for y1, y2, flag in d[x]:
            if flag:
                H.add((y1, y2))
            else:
                H.remove((y1, y2))
        prev_x, prev_h = x, cal(H)
    return res

时间复杂度 O(N^2)，52 ms

目录

0850：矩形面积 II（2235 分）

题目

分析

解答