public boolean isRectangleCover(int[][] rectangles) {
if (rectangles == null || rectangles.length == 0) {
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[]>(){
public int compare(int[] p1, int[] p2) {
else if (p1[1] >= p2[3]) {
// There is an intersection in the y-interval, return 0 in TreeSet and set.add() will return false;
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;
y_interval -= points[3] - points[1];
// Found intersection in y_interval, cannot get perfect rectangle
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))) {
class Rectangle implements Comparable<Rectangle>{
public Rectangle(int x, int[] points, boolean 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;