https://leetcode.com/problems/perfect-rectangle/
// https://discuss.leetcode.com/topic/55944/o-n-log-n-sweep-line-solution
public class Solution {
public class Column implements Comparable<Column> {
int xs;
int[] rect;
public Column(int xs, int[] rect) {
this.xs = xs;
this.rect = rect;
}
public int compareTo(Column that) {
if (this.xs != that.xs) {
return this.xs - that.xs;
}
return this.rect[0] - that.rect[0];
}
}
public boolean isRectangleCover(int[][] rectangles) {
PriorityQueue<Column> pq = new PriorityQueue<Column>();
int[] border = {Integer.MAX_VALUE, Integer.MIN_VALUE};
for (int[] rect : rectangles) {
Column c1 = new Column(rect[0], rect);
Column c2 = new Column(rect[2], rect);
pq.add(c1);
pq.add(c2);
if (rect[1] < border[0]) {
border[0] = rect[1];
}
if (rect[3] > border[1]) {
border[1] = rect[3];
}
}
TreeSet<int[]> tset = new TreeSet<int[]> (new Comparator<int[]>(){
public int compare(int []rect1, int[]rect2) {
if (rect1[3] <= rect2[1]) {
return -1;
}
else if (rect1[1] >= rect2[3]) {
return 1;
}
else {
return 0;
}
}
});
int yRange = 0;
while (!pq.isEmpty()) {
int xs = pq.peek().xs;
while (!pq.isEmpty() && pq.peek().xs == xs) {
Column col = pq.poll();
int[] rect = col.rect;
if (xs == rect[2]) {
tset.remove(rect);
yRange -= rect[3] - rect[1];
}
else {
// xs == rect[0]
if (!tset.add(rect)) {
// intersect
return false;
}
yRange += rect[3] - rect[1];
}
}
// if pq.isEmpty(), the right line, no need to check
if (!pq.isEmpty() && yRange != border[1] - border[0]) {
return false;
}
}
return true;
}
}