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

如果所有矩形一起精确覆盖了某个矩形区域，则返回 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],[3,2,4,4]]
输出：false
解释：图形顶端留有空缺，无法覆盖成一个矩形。
示例 4：

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

思路1:①求所有矩形的面积和S_SUM

　　　②求所有点所能构成的最大矩形面积S_MAX

　　　③判断S_SUM==S_MAX

　　　④通过矩形之间的交集判断是否存在重叠

　　　 第④步复杂度O(N)^2,超时.

思路2:求所有点在矩形中出现的次数,一个合格的矩形应该只有4个只出现一次的点,同时其他点都是成对存在,比如不会有一个点出现在3个矩形顶点中的情况.

　　　求出这4个唯一的顶点之后,计算这4个顶点所围成的面积是否等于所有矩形的面积和

　　　

 1 from typing import List
 2 
 3 
 4 class Solution:
 5     def isRectangleCover(self, rectangles: List[List[int]]) -> bool:
 6         sum_area = 0
 7 
 8         point_map = {}
 9 
10         for rectangle in rectangles:
11             sum_area += self.compute_area(rectangle)
12             points = self.get_all_points(rectangle)
13             for point in points:
14                 if point_map.get(point, False):
15                     point_map[point] += 1
16                 else:
17                     point_map[point] = 1
18         return self.is_legal(point_map, sum_area)
19 
20     def compute_area(self, rectangle):
21         x1, y1, x2, y2 = rectangle
22         width = abs(x2 - x1)
23         height = abs(y2 - y1)
24         return width * height
25 
26     def get_all_points(self, rectangle):
27         x1, y1, x2, y2 = rectangle
28         left_down = (x1, y1)
29         left_up = (x1, y2)
30         right_down = (x2, y1)
31         right_up = (x2, y2)
32         return [left_down, left_up, right_down, right_up]
33 
34     def is_legal(self, point_map, sum_area):
35         single_points_times = 0
36 
37         x1_min = float('inf')
38         y1_min = float('inf')
39         x2_max = -float('inf')
40         y2_max = -float('inf')
41 
42         for k, v in point_map.items():
43             if v == 1:
44                 single_points_times += 1
45                 x1_min = min(x1_min, k[0])
46                 y1_min = min(y1_min, k[1])
47                 x2_max = max(x2_max, k[0])
48                 y2_max = max(y2_max, k[1])
49             elif v % 2 == 1:
50                 return False
51         return single_points_times == 4 and sum_area == self.compute_area([x1_min, y1_min, x2_max, y2_max])
52 
53 
54 # def has_overlap(self, rectangleA, rectangleB):
55 #     a_x1, a_y1, a_x2, a_y2 = rectangleA
56 #     b_x1, b_y1, ba_x2, b_y2 = rectangleB
57 #     left = max(a_x1, b_x1)
58 #     right = min(a_x2, ba_x2)
59 #     top = min(a_y2, b_y2)
60 #     bottom = max(a_y1, b_y1)
61 #     return not (left >= right or bottom >= top)