# C++ Just one loop, simple (not the best) AC solution

• Feel surprised that such as simple solution works. I just keep remembering the x2 of rectangles being parsed and remove the unnecessary checks when x2 <= x1 (impossible to overlap anymore)

``````static bool mycomp(vector<int>& a, vector<int>& b) {
return a[0] < b[0];
}

bool isRectangleCover(vector<vector<int>>& rectangles) {
if (rectangles.size() == 0) return 0;

sort(rectangles.begin(), rectangles.end(), mycomp); // sort by x1

map<int, vector<pair<int, int> > > checks; // x2 -> [(y1, y2), ...]
int l = INT_MAX, r = INT_MIN, u = INT_MAX, d = INT_MIN;
int area = 0;

for (int i = 0; i < rectangles.size(); i++) {
int x1 = rectangles[i][0], y1 = rectangles[i][1], x2 = rectangles[i][2], y2 = rectangles[i][3];

while(checks.size() > 0 && checks.begin()->first <= x1) checks.erase(checks.begin()); // no conflict

for (auto it = checks.begin(); it != checks.end(); it++) {
for (int j = 0; j < it->second.size(); j++) {
pair<int, int> check = it->second[j];
if (y2 > check.first && y1 < check.second) return false;
}
}

checks[x2].push_back(make_pair(y1, y2));

l = min(l, x1);
r = max(r, x2);
u = min(u, y1);
d = max(d, y2);
area += (x2 - x1) * (y2 - y1);
}

return (r - l) * (d - u) == area;
}
``````

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