# Question

Formatted question description: https://leetcode.ca/all/391.html

 391	Perfect Rectangle

Given N axis-aligned rectangles where N > 0, determine if they all together form an exact cover of a rectangular region.

Each rectangle is represented as a bottom-left point and a top-right point.
For example, a unit square is represented as [1,1,2,2]. (
coordinate of bottom-left point is (1, 1) and top-right point is (2, 2)).

Example 1:

rectangles = [
[1,1,3,3],
[3,1,4,2],
[3,2,4,4],
[1,3,2,4],
[2,3,3,4]
]

Return true. All 5 rectangles together form an exact cover of a rectangular region.

Example 2:

rectangles = [
[1,1,2,3],
[1,3,2,4],
[3,1,4,2],
[3,2,4,4]
]

Return false. Because there is a gap between the two rectangular regions.

Example 3:

rectangles = [
[1,1,3,3],
[3,1,4,2],
[1,3,2,4],
[3,2,4,4]
]

Return false. Because there is a gap in the top center.

Example 4:

rectangles = [
[1,1,3,3],
[3,1,4,2],
[1,3,2,4],
[2,2,4,4]
]

Return false. Because two of the rectangles overlap with each other.



# Algorithm

The four vertices of all rectangles can only have the following three situations: blue, green, and red, where blue means there are no other rectangles around the vertex, a T-shaped green dot means two rectangles are next to each other, and a red dot means four rectangles are adjacent to each other. adjacent,

Then in a perfect rectangle, there can only be four blue points, which is a very important criterion. Let’s look at the four vertices of the rectangle again. Let’s label the vertices 1, 2, 4, and 8, in the order of bottom left, top left, top right, and bottom right. Why not 1, 2, 3, 4? Let’s pay attention to them. Binary 1(0001), 2(0010), 4(0100), 8(1000), which is convenient for us and OR operation.

Another criterion we need to know is that when a point is the lower left vertex of a certain rectangle, this point cannot be the lower left vertex of other rectangles. This condition must be true for these four vertices, then for each point If it is one of the four vertices of a certain rectangle, we record it. If it is the same vertex in other rectangles, then just return false directly, which reflects our mark as 1, 2, 4 , 8 benefits, we can check 1 bit by bit.

If the attributes of each point do not conflict, then we will verify whether the mask of each point is reasonable. Through the above analysis, we know that each point can only be one of the three cases of blue, green, and red, among which the blue case It is that there is only one 1 in the four bits of the mask, which are 1 (0001), 2 (0010), 4 (0100), 8 (1000), and there can only be four blue dots; then for the T-shaped green dot, mask There are two 1s in the four digits, then there are six situations, namely 12(1100), 10(1010), 9(1001), 6(0110), 5(0101), 3(0011); With the red dot, the four digits of the mask are all 1, and there is only one case of 15 (1111).

Then we can directly find the number of masks 1, 2, 4, and 8, or indirectly find the number of green dots and red dots to see if it is four. The last judgment condition is that the cumulative sum of each rectangular surface must be equal to the area of ​​the last large rectangle, then the area of ​​the large rectangle can be calculated by calculating the minimum lower left point and the maximum upper right point.

# Code

Java

• import java.util.HashSet;

public class Perfect_Rectangle {

public class Solution {
public boolean isRectangleCover(int[][] rectangles) {
if (rectangles.length == 0 || rectangles[0].length == 0) {
return false;
} else {
HashSet<String> set = new HashSet<>();
int leftMost = Integer.MAX_VALUE;
int bottomMost = Integer.MAX_VALUE;
int rightMost = Integer.MIN_VALUE;
int topMost = Integer.MIN_VALUE;
int x1, y1, x2, y2;
long area = 0;
for (int[] rect : rectangles) {
x1 = rect[0];
y1 = rect[1];
x2 = rect[2];
y2 = rect[3];
area += (x2 - x1) * (y2 - y1);//累积记录已遍历的矩形的面积
//记录最靠边界的点的坐标
if (x1 < leftMost) {
leftMost = x1;
}
if (y1 < bottomMost) {
bottomMost = y1;
}
if (x2 > rightMost) {
rightMost = x2;
}
if (y2 > topMost) {
topMost = y2;
}
if (area > (rightMost - leftMost) * (topMost - bottomMost)) {
//目前遍历的矩形的面积已经大于了所能覆盖的面积，则一定存在了重叠
return false;
}
//由当前考察的矩形的四个顶点的坐标构成的键值
String key1 = x1 + "," + y1;
String key2 = x1 + "," + y2;
String key3 = x2 + "," + y1;
String key4 = x2 + "," + y2;
//totalCouverCount用以记录是否出现了某个矩形完全覆盖了之前的某个矩形
//删除那些出现了偶数次的键值
if (set.contains(key1)) {
set.remove(key1);
} else {
}

if (set.contains(key2)) {
set.remove(key2);
} else {
}

if (set.contains(key3)) {
set.remove(key3);
} else {
}

if (set.contains(key4)) {
set.remove(key4);
} else {
}
}

if (area != (rightMost - leftMost) * (topMost - bottomMost)) {//说明没有完全覆盖或出现了重叠覆盖
return false;
}

String key1 = leftMost + "," + bottomMost;
String key2 = leftMost + "," + topMost;
String key3 = rightMost + "," + bottomMost;
String key4 = rightMost + "," + topMost;
if (set.size() != 4 || !set.contains(key1) ||
!set.contains(key2) || !set.contains(key3) ||
!set.contains(key4)) {
return false;
} else {
return true;
}
}
}
}
}

• Todo

• import heapq

class Solution(object):
def isRectangleCover(self, rectangles):
"""
:type rectangles: List[List[int]]
:rtype: bool
"""
leftBound = rectangles[0][0]
rightBound = rectangles[0][2]
bottomBound = rectangles[0][1]
topBound = rectangles[0][3]
lines = []
realArea = 0
for rect in rectangles:
leftBound = min(leftBound, rect[0])
rightBound = max(rightBound, rect[2])
bottomBound = min(bottomBound, rect[1])
topBound = max(topBound, rect[3])
realArea += (rect[3] - rect[1]) * (rect[2] - rect[0])
lines.append((rect[0], 1, rect[1], rect[3]))
lines.append((rect[2], -1, rect[1], rect[3]))
area = (rightBound - leftBound) * (topBound - bottomBound)
if area != realArea:
return False
lines.sort()
bst = []
for line in lines:
x, flag, bottom, top = line
if flag > 0:
idx = bisect.bisect_right(bst, (bottom, top))
bisect.insort_right(bst, (bottom, top))
if idx + 1 < len(bst) and bst[idx + 1][0] < bst[idx][1] or idx > 0 and bst[idx][0] < bst[idx - 1][1]:
return False
else:
bst.remove((bottom, top))
return area == realArea