# JAVA Solution with priorityQueue, come layer by layer beat 99%, with detailed explanation

• When I saw this problem, I just thought that if we sort the rectangle with rules like:
(1) with the start point `y`in increasing sequence `rectangles[i][1]`
(2) if has the same `y` value we just sort by the `x` value of start point `rectangles[i][0]`
then the rectangles will have these attributions:
(1) the rectangle with the same height will be together
then we traverse through the sorted array:
we will find that each time the next rectangle has the same start `y` with the former must has the same start point by the right bottom point of the former, if not return false
then we use a priorityQueue to store the segment which record a same base height line combined by the same start `y` the comparator is the height, so what we do is to from left to right, from bottom to up to splice a final rectangle, if we met the Repeat area or vacancy we will return false; we have sorted the rectangles and the rest of rectangle will not Make up for vacancies.
Just write a test case

``````[[0,0,4,1],[7,0,8,2],[6,2,8,3],[5,1,6,3],[4,0,5,1],[6,0,7,2],[4,2,5,3],[2,1,4,3],[0,1,2,2],[0,2,2,3],[4,1,5,2],[5,0,6,1]]
``````

After sorted

``````[[0,0,4,1],[4,0,5,1],[5,0,6,1],[6,0,7,2],[7,0,8,2],[0,1,2,2],[2,1,4,3],[4,1,5,2],[5,1,6,3],[0,2,2,3],[4,2,5,3],[6,2,8,3]]
``````

After first combination we get the following shape

The segment after combine is `[0, 6, h:1], [6, 8, h:3], i=5`
After second loop

The shadow rectangle is added the`i=9`
And we have 5 segment`[0,2,h:2],[2,4,h:3],[4,5,h:2],[5,6,h:3], [6,8,h:2]` in priorityQueue
Then left-up,then middle up , then left up
Then is an rectangle ,
`The main thought is add layer by layer`
Show the code :

``````class Segment {
int start;
int end;
int height;
Segment(int start, int end, int height){
this.start = start;
this.end = end;
this.height = height;
}
}
public boolean isRectangleCover(int[][] rectangles) {
final boolean[] tag = {false};
Arrays.sort(rectangles, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if (o1[1] == o2[1] && o1[0] == o2[0]) {
tag[0] = true;
return -1;
}else if (o1[1] == o2[1])return o1[0] - o2[0];
else return o1[1] - o2[1];
}
});
if (tag[0]) return false;
PriorityQueue<Segment> que = new PriorityQueue<>(new Comparator<Segment>() {
@Override
public int compare(Segment o1, Segment o2) {
if (o1.height == o2.height) {
return o1.start - o2.start;
}
return o1.height - o2.height;
}
});

int i = solve (0, rectangles[0][0], -1, rectangles[0][1], rectangles, que);
if (i == -1) return false;
while (i < rectangles.length) {
Segment seg = que.poll();
while (!que.isEmpty()) {
Segment tmp = que.peek();
if (tmp.height != seg.height || tmp.start != seg.end) break;
seg.end = que.poll().end;
}
if (rectangles[i][0] != seg.start || rectangles[i][1] != seg.height) return false;
i = solve(i,seg.start,seg.end,seg.height,rectangles,que);
if (i == -1) return false;
}
Segment seg = que.poll();
while (!que.isEmpty()) {
Segment cur = que.poll();
if (cur.height != seg.height) {
return false;
}
}
return true;
}

private int solve(int i, int start, int limit,int base, int[][] rectangles, PriorityQueue<Segment> que) {
int end = start;
int h = rectangles[i][3];
for (; i < rectangles.length; i ++) {
if (end == limit) break;
if (rectangles[i][1] != base) {
if (limit == -1) {
if (rectangles[i][0] > end || rectangles[i][2] > end) return -1;
}else {
return -1;
}
break;
}
if (rectangles[i][0] != end) return -1;
if (h == rectangles[i][3]) {
end = rectangles[i][2];
}else {
que.offer(new Segment(start, end, h));
start = rectangles[i][0];
end = rectangles[i][2];
h = rectangles[i][3];
}
}
if (limit != -1 && end != limit) return -1;
que.offer(new Segment(start, end, h));
return i;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.