Sweep Line O(nlogn)

• Idea is very basic that we sweep line from left to right. the next event point is a left side of rectangle with smallest x value in heap. what made code a bit long is the case that there are multiple rectangles with the same left side value (the first value of the four).

new version

``````public boolean isRectangleCover(int[][] rectangles) {
int x1 = Integer.MAX_VALUE;
int x2 = Integer.MAX_VALUE;
int x3 = Integer.MIN_VALUE;
int x4 = Integer.MIN_VALUE;
for(int i=0; i<rectangles.length; i++) {
x1 = Math.min(x1, rectangles[i][0]);
x2 = Math.min(x2, rectangles[i][1]);
x3 = Math.max(x3, rectangles[i][2]);
x4 = Math.max(x4, rectangles[i][3]);
}
Arrays.sort(rectangles, (r1, r2)->{ return r1[0]!=r2[0]?r1[0]-r2[0]:r1[1]-r2[1];});
PriorityQueue<int[]> queue = new PriorityQueue<>((r1,r2)->{return r1[2]!=r2[2]?r1[2]-r2[2]:r1[3]-r2[3];});
queue.offer(new int[]{Integer.MIN_VALUE,x2,rectangles[0][0],x4});
for(int i=0; i<rectangles.length; ) {
List<int[]> oldRect = new ArrayList<>();
List<int[]> newRect = new ArrayList<>();
int boundary = queue.peek()[2];
if(!check(oldRect, newRect)) return false;
}
return true;
}
public boolean check(List<int[]> r1, List<int[]> r2){
if(r1.size()==0||r2.size()==0) return false;
List<int[]> height1 = getHeight(r1);
List<int[]> height2 = getHeight(r2);
if(height1.size()!=height2.size()) return false;
for(int i=0; i<height1.size(); i++) if(height1.get(i)[0]!=height2.get(i)[0] || height1.get(i)[1]!=height2.get(i)[1]) return false;
return true;
}
public List<int[]> getHeight(List<int[]> r1) {
List<int[]> ans = new ArrayList<>();
int[] cur = new int[]{r1.get(0)[1],r1.get(0)[3]};
for(int i = 1; i<r1.size(); i++) {
if(cur[1]==r1.get(i)[1]) {
cur[1] = r1.get(i)[3];
} else {
cur = new int[]{r1.get(i)[1],r1.get(i)[3]};
}
}
return ans;
}
``````

old version

``````class Interval {
int start;
int end;
public Interval(int a, int b) {
start = a;
end = b;
}
}
public boolean isRectangleCover(int[][] rectangles) {
if(rectangles.length==0) return false;
int[] biggest = new int[]{rectangles[0][0],rectangles[0][1],rectangles[0][2],rectangles[0][3]};
Map<Integer,List<Integer>> hm = new HashMap<>();
for(int i=0;i<rectangles.length;i++) {
biggest[0] = Math.min(biggest[0],rectangles[i][0]);
biggest[1] = Math.min(biggest[1],rectangles[i][1]);
biggest[2] = Math.max(biggest[2],rectangles[i][2]);
biggest[3] = Math.max(biggest[3],rectangles[i][3]);
if(!hm.containsKey(rectangles[i][0])) hm.put(rectangles[i][0], new ArrayList<>());
}
for(List<Integer> l:hm.values()) {
Collections.sort(l,(i1,i2)->rectangles[i1][1]-rectangles[i2][1]);
}

int line = biggest[0];
List<Interval> bound = new ArrayList<>();
PriorityQueue<Integer> pq = new PriorityQueue<>((i1,i2)->{
if(rectangles[i1][2]!=rectangles[i2][2]) return rectangles[i1][2]-rectangles[i2][2];
else return rectangles[i1][1]-rectangles[i2][1];
});
int visited = 0;
while(line<biggest[2]) {
List<Integer> cur = hm.get(line);
if(cur==null) return false;
int i = 0;
int j = 0;
while(j<bound.size()) {
int low = bound.get(j).start;
int high = bound.get(j).end;
while(i<cur.size()&&low<high) {
int index = cur.get(i++);
if(rectangles[index][1]!=low) return false;
low = rectangles[index][3];
pq.offer(index);
visited++;
}
j++;
if(low>high) return false;
}
int next = pq.poll();
line = rectangles[next][2];
bound = new ArrayList<>();
int high = rectangles[next][3];
while(!pq.isEmpty()&&rectangles[pq.peek()][2]==rectangles[next][2]) {
int curIndex = pq.poll();
if(high!=rectangles[curIndex][1]) {
high = rectangles[curIndex][3];
} else {
bound.get(bound.size()-1).end = rectangles[curIndex][3];
high = rectangles[curIndex][3];
}
}

}
return visited==rectangles.length;
}
``````

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