Google
391 Perfect Rectangle

1. Question

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:
1
rectangles = [
2
[1,1,3,3],
3
[3,1,4,2],
4
[3,2,4,4],
5
[1,3,2,4],
6
[2,3,3,4]
7
]
8
9
Return true. All 5 rectangles together form an exact cover of a rectangular region.
Copied!
Example 2:
1
rectangles = [
2
[1,1,2,3],
3
[1,3,2,4],
4
[3,1,4,2],
5
[3,2,4,4]
6
]
7
8
Return false. Because there is a gap between the two rectangular regions.
Copied!
Example 3:
1
rectangles = [
2
[1,1,3,3],
3
[3,1,4,2],
4
[1,3,2,4],
5
[3,2,4,4]
6
]
7
Return false. Because there is a gap in the top center.
Copied!
Example 4:
1
rectangles = [
2
[1,1,3,3],
3
[3,1,4,2],
4
[1,3,2,4],
5
[2,2,4,4]
6
]
7
8
Return false. Because two of the rectangles overlap with each other.
Copied!

2. Implementation

(1) Scan Line + Heap + TreeSet
思路:
1.首先我们定义一个Rectangle的类,其中包含对应的其属于rectangle的所有点的信息,以及这个rectangle的x是一个矩阵的左x还是右x这些信息。将每个点离散化,将左边和右边的x值分别定义一个Rectangle类,放在一个最小堆里
2.第二步,我们用一个TreeSet保存每个rectangle关于y点的信息,按照y值从小到大排序。这里对set的comparator,我们用了小技巧,如果两个rectangle的y interval相交,compare函数会返回0,这样当我们call set.add()的时候,set.add会返回0。
3.最后一步则是按照x的值从小到大的顺序,分别处理其对应矩阵的y interval,判断每个x点对应的y interval是否存在overlap或者gap,如果有则返回false
1
class Solution {
2
public boolean isRectangleCover(int[][] rectangles) {
3
if (rectangles == null || rectangles.length == 0) {
4
return false;
5
}
6
7
int top = Integer.MIN_VALUE, bottom = Integer.MAX_VALUE;
8
PriorityQueue<Rectangle> minHeap = new PriorityQueue();
9
10
// Sort points in ascending order based on x-interval, and find the max value and min value of y
11
for (int[] rectangle : rectangles) {
12
minHeap.add(new Rectangle(rectangle[0], rectangle, false));
13
minHeap.add(new Rectangle(rectangle[2], rectangle, true));
14
top = Math.max(top, rectangle[3]);
15
bottom = Math.min(bottom, rectangle[1]);
16
}
17
18
// Sort points in ascending order based on y-interval
19
Set<int[]> set = new TreeSet(new Comparator<int[]>(){
20
@Override
21
public int compare(int[] p1, int[] p2) {
22
if (p1[3] <= p2[1]) {
23
return -1;
24
}
25
else if (p1[1] >= p2[3]) {
26
return 1;
27
}
28
// There is an intersection in the y-interval, return 0 in TreeSet and set.add() will return false;
29
else {
30
return 0;
31
}
32
}
33
});
34
35
int y_interval = 0;
36
while (!minHeap.isEmpty()) {
37
int x = minHeap.peek().x;
38
// Handle the edge vertically
39
while (!minHeap.isEmpty() && x == minHeap.peek().x) {
40
Rectangle rect = minHeap.remove();
41
int[] points = rect.points;
42
43
if (rect.isEnd) {
44
set.remove(points);
45
y_interval -= points[3] - points[1];
46
}
47
else {
48
// Found intersection in y_interval, cannot get perfect rectangle
49
if (!set.add(points)) {
50
return false;
51
}
52
y_interval += points[3] - points[1];
53
}
54
}
55
56
// For perfect rectangle, the y_interval must be equal to the difference betwee top and bottom
57
// Otherwise, it means there is a vertical gap between rectangles
58
if (!minHeap.isEmpty() && (y_interval != (top - bottom))) {
59
return false;
60
}
61
}
62
return true;
63
}
64
65
class Rectangle implements Comparable<Rectangle>{
66
int x;
67
int[] points;
68
boolean isEnd;
69
70
public Rectangle(int x, int[] points, boolean isEnd) {
71
this.x = x;
72
this.points = points;
73
this.isEnd = isEnd;
74
}
75
76
// When there is an intersection for two rectangle at x, the rectangle with a smaller bottom left x should comes before the other
77
public int compareTo(Rectangle that) {
78
return this.x == that.x ? this.points[0] - that.points[0] : this.x - that.x;
79
}
80
}
81
}
Copied!
(2) HashSet
思路: 通过观察,我们发现如果所有矩形可以组成perfect rectangle,那么perfect rectangle的四个顶点必须只出现一次,其他地点出现偶数次,同时perfect rectangle的面积等于所有矩形的面积之和
1
class Solution {
2
public boolean isRectangleCover(int[][] rectangles) {
3
if (rectangles == null || rectangles.length == 0) {
4
return false;
5
}
6
7
int x1 = Integer.MAX_VALUE;
8
int x2 = Integer.MIN_VALUE;
9
int y1 = Integer.MAX_VALUE;
10
int y2 = Integer.MIN_VALUE;
11
12
Set<String> set = new HashSet<>();
13
int area = 0;
14
15
for (int[] rectangle : rectangles) {
16
x1 = Math.min(x1, rectangle[0]);
17
x2 = Math.max(x2, rectangle[2]);
18
y1 = Math.min(y1, rectangle[1]);
19
y2 = Math.max(y2, rectangle[3]);
20
21
area += (rectangle[2] - rectangle[0]) * (rectangle[3] - rectangle[1]);
22
23
String code1 = rectangle[0] + "#" + rectangle[1];
24
String code2 = rectangle[0] + "#" + rectangle[3];
25
String code3 = rectangle[2] + "#" + rectangle[1];
26
String code4 = rectangle[2] + "#" + rectangle[3];
27
28
if (!set.add(code1)) set.remove(code1);
29
if (!set.add(code2)) set.remove(code2);
30
if (!set.add(code3)) set.remove(code3);
31
if (!set.add(code4)) set.remove(code4);
32
}
33
34
if (set.size() != 4 || !set.contains(x1 + "#" + y1) || !set.contains(x1 + "#" + y2)
35
|| !set.contains(x2 + "#" + y1) || !set.contains(x2 + "#" + y2)) {
36
return false;
37
}
38
return area == (x2 - x1) * (y2 - y1);
39
}
40
}
Copied!

3. Time & Space Complexity

Scan Line + Heap + TreeSet: 时间复杂度O(nlogn), n是rectangle的个数, 空间复杂度O(n)
HashSet: 时间复杂度O(n), 空间复杂度O(n)