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.
class Solution {
public boolean isRectangleCover(int[][] rectangles) {
if (rectangles == null || rectangles.length == 0) {
return false;
}
int top = Integer.MIN_VALUE, bottom = Integer.MAX_VALUE;
PriorityQueue<Rectangle> minHeap = new PriorityQueue();
// Sort points in ascending order based on x-interval, and find the max value and min value of y
for (int[] rectangle : rectangles) {
minHeap.add(new Rectangle(rectangle[0], rectangle, false));
minHeap.add(new Rectangle(rectangle[2], rectangle, true));
top = Math.max(top, rectangle[3]);
bottom = Math.min(bottom, rectangle[1]);
}
// Sort points in ascending order based on y-interval
Set<int[]> set = new TreeSet(new Comparator<int[]>(){
@Override
public int compare(int[] p1, int[] p2) {
if (p1[3] <= p2[1]) {
return -1;
}
else if (p1[1] >= p2[3]) {
return 1;
}
// There is an intersection in the y-interval, return 0 in TreeSet and set.add() will return false;
else {
return 0;
}
}
});
int y_interval = 0;
while (!minHeap.isEmpty()) {
int x = minHeap.peek().x;
// Handle the edge vertically
while (!minHeap.isEmpty() && x == minHeap.peek().x) {
Rectangle rect = minHeap.remove();
int[] points = rect.points;
if (rect.isEnd) {
set.remove(points);
y_interval -= points[3] - points[1];
}
else {
// Found intersection in y_interval, cannot get perfect rectangle
if (!set.add(points)) {
return false;
}
y_interval += points[3] - points[1];
}
}
// For perfect rectangle, the y_interval must be equal to the difference betwee top and bottom
// Otherwise, it means there is a vertical gap between rectangles
if (!minHeap.isEmpty() && (y_interval != (top - bottom))) {
return false;
}
}
return true;
}
class Rectangle implements Comparable<Rectangle>{
int x;
int[] points;
boolean isEnd;
public Rectangle(int x, int[] points, boolean isEnd) {
this.x = x;
this.points = points;
this.isEnd = isEnd;
}
// When there is an intersection for two rectangle at x, the rectangle with a smaller bottom left x should comes before the other
public int compareTo(Rectangle that) {
return this.x == that.x ? this.points[0] - that.points[0] : this.x - that.x;
}
}
}