完美矩形

难度: Hard

给你一个数组 rectangles ，其中 rectangles[i] = [x_i, y_i, a_i, b_i] 表示一个坐标轴平行的矩形。这个矩形的左下顶点是 (x_i, y_i) ，右上顶点是 (a_i, b_i) 。

如果所有矩形一起精确覆盖了某个矩形区域，则返回 true ；否则，返回 false 。

示例 1：

输入：rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]
输出：true
解释：5 个矩形一起可以精确地覆盖一个矩形区域。

示例 2：

输入：rectangles = [[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]
输出：false
解释：两个矩形之间有间隔，无法覆盖成一个矩形。

示例 3：

输入：rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]]
输出：false
解释：因为中间有相交区域，虽然形成了矩形，但不是精确覆盖。

提示：

1 <= rectangles.length <= 2 * 10⁴
rectangles[i].length == 4
-10⁵ <= x_i, y_i, a_i, b_i <= 10⁵

Submission

运行时间: 66 ms

内存: 20.7 MB

class Solution:
    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:
        corners = set()
        area = 0
        for x1, y1, x2, y2 in rectangles:
            area += (x2 - x1) * (y2 - y1)
            corners ^= {(x1, y1), (x2, y2), (x1, y2), (x2, y1)}
        if len(corners) != 4:
            return False
        corners = sorted(corners)
        return area == (corners[-1][0] - corners[0][0]) * (corners[-1][1] - corners[0][1])

Explain

该题解的思路是通过计算所有矩形的面积之和，并记录所有矩形的四个顶点坐标。如果所有矩形恰好覆盖一个大矩形，那么所有矩形的面积之和应该等于最终大矩形的面积，并且除了最终大矩形的四个顶点外，其余顶点都应该出现偶数次（因为每个内部顶点都是两个矩形的交点）。最后，通过比较面积和顶点坐标来判断是否恰好覆盖。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:
        corners = set()
        area = 0
        for x1, y1, x2, y2 in rectangles:
            # 计算当前矩形的面积，并累加到总面积中
            area += (x2 - x1) * (y2 - y1)
            # 记录当前矩形的四个顶点坐标，使用异或操作来统计每个顶点出现的次数
            corners ^= {(x1, y1), (x2, y2), (x1, y2), (x2, y1)}
        # 如果最终剩下的顶点数量不等于4，说明不能恰好覆盖一个大矩形
        if len(corners) != 4:
            return False
        # 对剩下的四个顶点坐标进行排序
        corners = sorted(corners)
        # 比较所有矩形的面积之和与最终大矩形的面积是否相等
        return area == (corners[-1][0] - corners[0][0]) * (corners[-1][1] - corners[0][1])

Explore

异或操作用于顶点的管理在记录顶点出现次数时非常有效，因为每对相同的顶点异或两次后会消除，最终留下的是出现奇数次的顶点。这种方法可能会失败的情况是：如果有多余四个顶点出现奇数次，或者出现奇数次的顶点形成的不是矩形。此外，如果矩形的顶点由于精度问题（如浮点数计算误差）而被错误地认为是不同顶点，异或操作也可能导致错误结果。

题解假设所有小矩形合并成一个完美的大矩形。在这种情况下，理想的大矩形应该只有四个角落的顶点，这四个顶点分别是最小的x和y的组合，最小的x和最大的y的组合，最大的x和最小的y的组合，以及最大的x和最大的y的组合。内部任何交点或边界顶点在完美覆盖的情况下都会被相邻矩形顶点抵消，因此只剩下四个外围顶点。

是的，题解的方法假设所有小矩形合并为一个无间隙、无重叠的完美大矩形。如果存在矩形之间的重叠或者矩形之间完全不接触的空隙，那么这些情况都不符合完美矩形的条件。在这些情况下，小矩形的总面积将不等于大矩形的面积，或者顶点的处理（特别是异或消除）将无法正确反映所有小矩形构成大矩形的情况。

题解使用异或操作来自动处理重复顶点，因为任何顶点如果出现两次，其异或结果会归零，即消除该顶点。如果一个顶点恰好出现四次（两个矩形共用一边），它也会被消除。这种处理确保只有出现奇数次的顶点被保留。然而，这种方法假设矩形完美拼接，没有重叠和空隙。如果处理的数据或场景不符合这种假设，算法的准确性将受影响。