Yesterday, I meet a hard problem on Google onsite, of course, I do not finished to solve it in the limited time, I am really depressed as most of my classmates are asked to solve some much more easy problem set.

So let us check the problem directly ....

**Given N rectangle in the plane, how to check whether all the rectangle can form a big rectangle exactly !**

To make it clear, the interviewer mean that all the matrix should have no gap in between and no overlap to form a big rectangle !

At the first glance, I just think a brute force solution to sweep from the left most edge to the most right edge and check whether along all the edges we can fill the big rectangle exactly !. ... So finally, my method is a little messy, I just can not implement elegently....So you know what happened next ...... Goodbye, Google.....

Let us first check out a easy solution :

**We can just calculate all the rectangle area, and check whether the overall area equal the most outer rectangle area. Then we just need to check whether there exists 2 rectangle interact in the plane !**

Here is basic implementation by myself ....

```
struct Rect {
int x0, x1, y0, y1;
};
class Solution {
bool rect_overlap(Rect& a, Rect& b) {
if (a.x0 > b.y0 || b.x0 > a.y0) { return false; }
if (a.y0 > b.y1 || b.y0 < a.y1) { return false; }
return true;
}
int rect_area(Rect &a) {
return (y1 - y0) * (x1 - x0);
}
bool rect_check(vector<Rect> &rects) {
int n = rects.size();
long long sum_area = 0;
int xx0 = rects[0].x0, yy0 = rects[0].y0;
int xx1 = rects[1].x1, yy1 = rects[0].y1;
for (int i = 0; i < n; i++) {
xx0 = min(rects[i].x0, xx0);
yy0 = min(rects[i].y0, yy0);
xx1 = max(rects[i].x1, xx1);
yy1 = max(rects[i].y1, yy1);
sum_area += rect_area(rects[i]);
for (int j = i + 1; j < n; j++) {
if (rect_overlap(rects[i], rects[j])) {
return false;
}
}
}
return sum_area == (xx1 - xx0) * (yy1 - yy0);
}
};
```

* Hehe, of course this time complexicity is O(N^2) ! But we want O(NlogN) ....**

Let us change the orginal problem into a new problem :

**Problem Def :**

**Given N rectangle in the plane, how to check whether there are 2 rectangle overlap in NlogN time cost**

To solve this problem, I strong recommend you to refer the post by a Chinese guy

The main ideas is to use the plane swap ideas to solve the problem !

We will split the plane along all the edges of the rectangle and swap all the lines from left to right !

I will not delve into the details, just give you the template to know the key ideas behind the problem ...

```
class SegmentTree {
void Init() ;
void Insert(int left , int right);
void Delete(int left , int right);
void hasIntersect(int left , int right);
};
class Solution {
boolean has_rectangle_intersect(rectangle r[] , int n) {
map all the {r[0].left_x , r[0].right_x , ... ,
r[n-1].left_x , r[n-1].right_x} to the mapx[] ;
for( i = 0 ; i < n ; ++ i){
event[i<<1] = {r[i].left_x , r[i].down_y , r[i].up_y , +1 } ;
event[(i<<1)|1] = {r[i].right_x, r[i].down_y , r[i].up_y , -1 } ;
}
sort event[0..2*n-1] based on x in increasing order
tree.init() ;
for( i = 0 ; i < n<<1 ; ++ i){
if( event[i] is insert event){
if( tree.hasIntersection(event[i].down_y , event[i].up_y) )
return true ;
tree.Insert(event[i].down_y , event[i].up_y) ;
}else{
tree.Delete(event[i].down_y , event[i].up_y);
}
}
return false ;
}
};
```