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
    Y

    @yang202 Sorry but I don't know how to format the codes. It looks like plain texts. How to make it formatted as source codes?


  • 0

    Just do what the editor field tells you when you start a new post, put three backticks above and under the code. You can also find instructions when you click the question mark after "COMPOSE" in the editor field.


  • 0
    P

    Hi @yang202 I used a similar approach but instead of area, I counted the number of cells. My code works for 26 of the 27 test cases for submission. But it fails for one. I think the case it misses is if there are overlaps and gaps with equal amount so that they cancel each other. That is a condition necessary for completeness, which does not seem to be satisfied here.

    In case anyone wants, this is how the code looks like

    class Solution(object):
    
        INF_MAX = 99999999
        INF_MIN = -9999999
    
        def cellCount(self, rect):
            cols = rect[3] - rect[1]
            rows = rect[2] - rect[0]
            return cols*rows
    
        def isRectangleCover(self, rectangles):
            """
            :type rectangles: List[List[int]]
            :rtype: bool
            """
            bb = [self.INF_MAX, self.INF_MAX, self.INF_MIN, self.INF_MIN]
            rectCellCount = 0
            for rect in rectangles:
                bb[0] = min(bb[0], rect[0])
                bb[1] = min(bb[1], rect[1])
                bb[2] = max(bb[2], rect[2])
                bb[3] = max(bb[3], rect[3])
                rectCellCount += self.cellCount(rect)
            bbCellCount = self.cellCount(bb)
            return bbCellCount == rectCellCount
    

Log in to reply
 

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