C++ Simple Solution with Explanation


  • 0

    two rules:

    1. The sum of rectangles' area must equal to the final rectangle
    2. No overlap (Edge points exist 1 times)
    class Solution {
    public:
        bool isRectangleCover(vector<vector<int>>& rectangles) {
            int area = 0, bot_x = INT_MAX, bot_y = INT_MAX, top_x = INT_MIN, top_y = INT_MIN;
            unordered_map<int, unordered_map<int, int>> mp;
            for (auto& rec : rectangles) {
                int x1 = rec[0], y1 = rec[1], x2 = rec[2], y2 = rec[3];
                area += (y2 - y1) * (x2 - x1);
                mp[x1][y1]++;
                mp[x2][y2]++;
                mp[x1][y2]++;
                mp[x2][y1]++;
                bot_x = min(bot_x, x1);
                bot_y = min(bot_y, y1);
                top_x = max(top_x, x2);
                top_y = max(top_y, y2);
            }
            if ((top_x - bot_x) * (top_y - bot_y) != area) { // area judge
                return false;
            }
            for (auto& i : mp) {
                for (auto& j : i.second) {
                    if ((i.first == bot_x || i.first == top_x) && (j.first == bot_y || j.first == top_y) && j.second != 1)
                        return false; // edge points can only exist 1 times
                    if (j.second & 1) { // points which exist even times must be edge points
                        if ((i.first == bot_x || i.first == top_x) && (j.first == bot_y || j.first == top_y))
                            continue;
                        return false;
                    }
                }
            }
            return true;
        }
    };
    

Log in to reply
 

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