# O(sqrt(N)) extra Space, O(NlogN) Time solution.

• It is average case O(sqrt(n)) space solution (worst case still O(n))
I will add more explanation when I got time.

struct Pos {int x, y;};
struct CompareIter{
bool operator()(list<Pos>::iterator ia, list<Pos>::iterator ib){
return make_pair(ia->y, ia->x) > make_pair(ib->y, ib->x);// i.e. ia->y < ib->y || (ia->y == ib->y && ia->x < ib->x);
}
};
class Histogram
{
list<Pos> outline;
bool is_first_layer_done = false;
priority_queue<list<Pos>::iterator, vector<list<Pos>::iterator>, CompareIter> lcorner_heap;
public:
//assume no invalid rectangles
{
Pos topleft {rect[0], rect[3]}, bottomright {rect[2], rect[1]};
if (outline.empty()) //First time, set up the "base block".
{
outline.push_back(topleft);
outline.push_back(bottomright);
lcorner_heap.push(outline.begin());
lcorner_heap.push(++outline.begin());
return true;
}
//assert lcorner_heap.size() > 0
auto lcorner_iter = lcorner_heap.top();
lcorner_heap.pop();
if (lcorner_iter->x != topleft.x || lcorner_iter->y != bottomright.y)
{
if (!is_first_layer_done)
{
is_first_layer_done = true;
}
return false;
}
//assert: nextpos_iter will never be outline.end() after first layer is done.
auto nextpos_iter = next(lcorner_iter);
if (nextpos_iter == outline.end() || nextpos_iter->x > bottomright.x)
lcorner_heap.push(outline.insert(nextpos_iter, bottomright));
else if (nextpos_iter->x < bottomright.x)
return false;
else if (nextpos_iter->y < topleft.y && nextpos_iter->y > bottomright.y)
lcorner_heap.push(nextpos_iter);
else if (nextpos_iter->y == topleft.y)
outline.erase(nextpos_iter);
*lcorner_iter = topleft;
if (lcorner_iter == outline.begin() || prev(lcorner_iter)->y > topleft.y)
lcorner_heap.push(lcorner_iter);
else if (prev(lcorner_iter)->y == topleft.y)
outline.erase(lcorner_iter);
return true;
}
bool isRectangle()
{
return outline.size() == 2;
}
};

class Solution {
public:
bool isRectangleCover(vector<vector<int>>& rectangles) {
sort(rectangles.begin(), rectangles.end(), [] (vector<int> va, vector<int> vb){
return make_pair(va[1], va[0]) < make_pair(vb[1], vb[0]);});
Histogram hist;
for (auto & rect : rectangles)