# O(NlogN) But You Can Learn A Lot

• O(NlogN) But You Can Learn A Lot
The credit is given to https://discuss.leetcode.com/topic/55944/o-n-log-n-sweep-line-solution

``````public class Solution {
class Rect implements Comparable<Rect> {
int u, d, l, r;

public Rect(int[] rect) {
l = rect[0]; d = rect[1]; r = rect[2]; u = rect[3];
}

public int compareTo(Rect that) {
if (this.u <= that.d)
return -1;
else if (this.d >= that.u)
return 1;
else
return 0; //Overlap, VERY IMPORTANT PROPERTY for TreeSet to check overlap
}
}

class RectLife implements Comparable<RectLife> {
int time;
boolean isEnd;
Rect rect;

public RectLife(int t, boolean ed, Rect rectt) {
time = t; isEnd = ed; rect = rectt;
}

public int compareTo(RectLife that) { //Important to also sort rect.l
return (this.time != that.time) ? this.time - that.time : this.rect.l - that.rect.l;
}
}

public boolean isRectangleCover(int[][] rectangles) {
PriorityQueue<RectLife> pq = new PriorityQueue();
TreeSet<Rect> set = new TreeSet();
int bot = rectangles[0][1], top = rectangles[0][3];

for (int[] rt : rectangles) {
Rect rect = new Rect(rt);
bot = Math.min(bot, rect.d);
top = Math.max(top, rect.u);

pq.offer(new RectLife(rect.l, false, rect));
pq.offer(new RectLife(rect.r, true, rect));
}

if (pq.isEmpty())
return false;

int height = 0;
while (!pq.isEmpty()) {
int time = pq.peek().time;

while (!pq.isEmpty() && pq.peek().time == time) {
RectLife rl = pq.poll();
if (!rl.isEnd) {
height += rl.rect.u - rl.rect.d;
else
//set considers there's already a 'same' component, while we defined:
//for Rect, 'same' is overlapping.
return false;
} else {
set.remove(rl.rect);
height -= rl.rect.u - rl.rect.d;
}
}

if (!pq.isEmpty() && height != top - bot)
return false;
}

return true;
}
}
``````

• Basic idea:
Sort by x-coordinate by PriorityQueue.
Insert y-interval into TreeSet, and check if there are overlapped rectangles.
Delete y-interval for ending rectangles from TreeSet.

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