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类，放在一个最小堆里
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
13
14
top = Math.max(top, rectangle);
15
bottom = Math.min(bottom, rectangle);
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 <= p2) {
23
return -1;
24
}
25
else if (p1 >= p2) {
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 - points;
46
}
47
else {
48
// Found intersection in y_interval, cannot get perfect rectangle
49
50
return false;
51
}
52
y_interval += points - points;
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 - that.points : this.x - that.x;
79
}
80
}
81
}
Copied!
(2) HashSet

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);
17
x2 = Math.max(x2, rectangle);
18
y1 = Math.min(y1, rectangle);
19
y2 = Math.max(y2, rectangle);
20
21
area += (rectangle - rectangle) * (rectangle - rectangle);
22
23
String code1 = rectangle + "#" + rectangle;
24
String code2 = rectangle + "#" + rectangle;
25
String code3 = rectangle + "#" + rectangle;
26
String code4 = rectangle + "#" + rectangle;
27
28
29
30
31
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)