Why my solution is wrong? Used area to verify.


  • 0
    Y

    I thought this would be correct, it works for the four test cases given in the problem description but unfortunately failed for other test cases when submitted.

    I first find the minx, maxx, miny, maxy. These four bounds determines a hull. The idea is that if there is no overlaps or gaps, then the area of the hull should be the sum of the areas of all rectangles. So what's wrong with this idea?

    class Solution {
    public:
    bool isRectangleCover(vector<vector<int>>& rectangles) {
    int xmin=INT_MAX,xmax=INT_MIN,ymin=INT_MAX,ymax=INT_MIN;
    for(int i=0;i<rectangles.size();++i){
    vector<int> tmp_rect = rectangles[i];
    xmin = min(min(tmp_rect[0],tmp_rect[2]),xmin);
    xmax = max(max(tmp_rect[0],tmp_rect[2]),xmax);
    ymin = min(min(tmp_rect[1],tmp_rect[3]),ymin);
    ymax = max(max(tmp_rect[1],tmp_rect[3]),ymax);
    }
    long real_area = 0;
    for(int i=0;i<rectangles.size();++i){
    vector<int> tmp_rect = rectangles[i];
    real_area += abs(tmp_rect[2]-tmp_rect[0]) * abs(tmp_rect[3]-tmp_rect[1]);
    }
    long ideal_area = (xmax-xmin)*(ymax-ymin);
    // cout << ideal_area << " " << real_area << endl;
    return (ideal_area==real_area);
    }
    };


  • 0

    If there are overlaps and gaps, and they add up nicely, then the area will match, but the answer should be false. The simplest example: imagine a 2x2 square covered with one 2x1 rectangle and two 1x1 squares. Now shift one of the squares onto the rectangle. The total area is still 4, but you have one 1x1 gap and one 1x1 overlap.

    And please format your code.


Log in to reply
 

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