What is the optimal approach for solving Rectangle Area II?

The optimal approach is to combine the Array and Segment Tree data structures with the Line Sweep technique to efficiently calculate the area while managing overlaps.

Why is a Segment Tree needed for this problem?

A Segment Tree helps efficiently manage and update the covered intervals for each vertical line sweep, ensuring accurate area calculation even with overlapping rectangles.

How does the Line Sweep technique work for Rectangle Area II?

The Line Sweep technique processes the rectangles by their x-coordinates, updating the Segment Tree for each rectangle's vertical projection. This allows for accurate tracking of overlapping regions.

Why do we use modulo 10^9 + 7 in this problem?

The modulo operation is used to ensure that the resulting area does not exceed the maximum allowed value, which is 10^9 + 7, as the answer may be too large to store in standard data types.

What are the time and space complexities of the solution?

The time complexity is O(N^2), where N is the number of rectangles, due to the line sweep and Segment Tree updates. The space complexity is O(N) for storing the Segment Tree and intermediate results.

#850

Hard

auto_awesome数组·结合·segment·树

LeetCode 题解工作台

矩形面积 II

给你一个轴对齐的二维数组 rectangles 。对于 rectangle[i] = [x1, y1, x2, y2] ，其中 (x i1 , y i1 ) 是该矩形左下角的坐标， (x i2 , y i2 ) 是该矩形右上角的坐标。计算平面中所有 rectangles 所覆盖的总面积…

数组线段树扫描线有序集合

题目描述

给你一个轴对齐的二维数组 rectangles 。对于 rectangle[i] = [x1, y1, x2, y2]，其中 (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⁹
x_i1<= x_i2
y_i1<= y_i2
所有矩阵面积不为 0。

lightbulb

解题思路

方法一：离散化 + 线段树 + 扫描线

线段树将整个区间分割为多个不连续的子区间，子区间的数量不超过 $log(width)$ 。更新某个元素的值，只需要更新 $log(width)$ 个区间，并且这些区间都包含在一个包含该元素的大区间内。区间修改时，需要使用懒标记保证效率。

线段树的每个节点代表一个区间；
线段树具有唯一的根节点，代表的区间是整个统计范围，如 $[1, N]$ ；
线段树的每个叶子节点代表一个长度为 1 的元区间 $[x, x]$ ；
对于每个内部节点 $[l, r]$ ，它的左儿子是 $[l, mid]$ ，右儿子是 $[mid + 1, r]$ , 其中 $mid = ⌊(l + r) / 2⌋$ (即向下取整)。

对于本题，线段树节点维护的信息有：

区间被覆盖的次数 cnt；
区间被覆盖的长度 len。

另外，由于本题利用了扫描线本身的特性，因此，区间修改时，不需要懒标记，也无须进行 pushdown 操作。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

class Node:
    def __init__(self):
        self.l = self.r = 0
        self.cnt = self.length = 0


class SegmentTree:
    def __init__(self, nums):
        n = len(nums) - 1
        self.nums = nums
        self.tr = [Node() for _ in range(n << 2)]
        self.build(1, 0, n - 1)

    def build(self, u, l, r):
        self.tr[u].l, self.tr[u].r = l, r
        if l != r:
            mid = (l + r) >> 1
            self.build(u << 1, l, mid)
            self.build(u << 1 | 1, mid + 1, r)

    def modify(self, u, l, r, k):
        if self.tr[u].l >= l and self.tr[u].r <= r:
            self.tr[u].cnt += k
        else:
            mid = (self.tr[u].l + self.tr[u].r) >> 1
            if l <= mid:
                self.modify(u << 1, l, r, k)
            if r > mid:
                self.modify(u << 1 | 1, l, r, k)
        self.pushup(u)

    def pushup(self, u):
        if self.tr[u].cnt:
            self.tr[u].length = self.nums[self.tr[u].r + 1] - self.nums[self.tr[u].l]
        elif self.tr[u].l == self.tr[u].r:
            self.tr[u].length = 0
        else:
            self.tr[u].length = self.tr[u << 1].length + self.tr[u << 1 | 1].length

    @property
    def length(self):
        return self.tr[1].length


class Solution:
    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        segs = []
        alls = set()
        for x1, y1, x2, y2 in rectangles:
            segs.append((x1, y1, y2, 1))
            segs.append((x2, y1, y2, -1))
            alls.update([y1, y2])

        segs.sort()
        alls = sorted(alls)
        tree = SegmentTree(alls)
        m = {v: i for i, v in enumerate(alls)}
        ans = 0
        for i, (x, y1, y2, k) in enumerate(segs):
            if i:
                ans += tree.length * (x - segs[i - 1][0])
            tree.modify(1, m[y1], m[y2] - 1, k)
        ans %= int(1e9 + 7)
        return ans

speed

复杂度分析

指标	值
时间	O(N^2)
空间	O(N)

psychology

面试官常问的追问

外企场景

question_mark
Candidate demonstrates understanding of the Line Sweep technique.
question_mark
Candidate effectively utilizes Segment Tree to manage overlapping intervals.
question_mark
Candidate correctly handles the modulo operation for large results.

warning

常见陷阱

外企场景

error
Misunderstanding the use of the Segment Tree and treating each rectangle independently.
error
Failing to handle large coordinate values properly, leading to inefficient solutions.
error
Neglecting the modulo operation when calculating the final area.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allowing rectangles with negative coordinates.
arrow_right_alt
Optimizing for rectangles with many overlapping areas.
arrow_right_alt
Handling different types of non-rectangular shapes, such as polygons.

help

常见问题

外企场景

继续练习

#218 天际线问题 #731 我的日程安排表 II #729 我的日程安排表 I