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


  • 0
    Y

    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;
        }
    

Log in to reply
 

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