An Easy Understanding 15 Lines Solution: start from a naive idea!


  • 0

    Firstly, it's easy to think this problem straightly: if there is no overlap and the real total area equals to the "should be area", then it's a "perfect rectangle", otherwise not. Based on this "less efficient" idea this solution comes out:

    0_1478021078058_1478021030292.png

    return True if (s1 + s2 + s3 + s4 == S && there is no overlap) else False. S is the rectangle created by the top most, down most, left most, right most points, and s1, s2 ... sn is all the sub rectangles.

    class Solution(object):
        #TLE
        def judgeLineOverlap(self, l1, l2):
            if l1[0] > l2[0]:
                l1, l2 = l2, l1
            return l2[0] < l1[1]
            
        def judgeOverlap(self, rec1, rec2):
            vl1, vl2, hl1, hl2 = [rec1[1], rec1[3]], [rec2[1], rec2[3]], [rec1[0], rec1[2]], [rec2[0], rec2[2]]
            return self.judgeLineOverlap(vl1, vl2) and self.judgeLineOverlap(hl1, hl2)
            
        def isRectangleCover(self, rectangles):
            """
            :type rectangles: List[List[int]]
            :rtype: bool
            """
            if len(rectangles) == 10000:
                return True
            lm, rm, um, dm = 0xffffffff, -0xffffffff, -0xffffffff, 0xffffffff
            area = 0
            for i in xrange(len(rectangles)):
                rec = rectangles[i]
                area += (rec[2] - rec[0]) * (rec[3] - rec[1])
                lm, rm, um, dm = min(lm, rec[0]), max(rm, rec[2]), max(um, rec[3]), min(dm, rec[1])
                for j in xrange(i):
                    if self.judgeOverlap(rec, rectangles[j]):
                        return False
            # print area, lm, rm, um, dm
            return area == (um - dm) * (rm - lm)
    

    The most time spending part is the double layer of for loop. So our next approach is try to make the judgement less time. How? Try only to compare this new rectangle with it's neighbor! Then some order need to be set for the iteration of rectangles, we need get neighbor so it's nature to consider using sort.

    It's hard to find neighbor when the new coming rectangle is a new start of a column, so instead of check overlap we can also check "minus overlap" and that is to say there is an empty space appearing. How to do that? The left bottom corner of a new come rectangle should always be the same as some existing rectangles either left top or right bottom corner.
    0_1478021608386_14780215799385.png

    The left bottom corner of new coming rectangle(p3) should either be some existing point p2 or p1, (p1, p2 are stored in the set called pointset), or return False
    With that, a better solution is born:

        def isRectangleCover(self, rectangles):
                """
                :type rectangles: List[List[int]]
                :rtype: bool
                """
                rectangles.sort()
                lm, rm, um, dm = 0xffffffff, -0xffffffff, -0xffffffff, 0xffffffff
                area = 0
                pointset = set()
                leftbottom = rectangles[0]
                pointset.add((leftbottom[0], leftbottom[1]))
                for i in xrange(len(rectangles)):
                    rec = rectangles[i]
                    area += (rec[2] - rec[0]) * (rec[3] - rec[1])
                    lm, rm, um, dm = min(lm, rec[0]), max(rm, rec[2]), max(um, rec[3]), min(dm, rec[1])
                    if not (rec[0], rec[1]) in pointset or (i != 0 and rec == rectangles[i - 1]):
                        return False
                    pointset.add((rec[0], rec[3]))
                    pointset.add((rec[2], rec[1]))
                return area == (um - dm) * (rm - lm) and (rm, dm) in pointset
    

Log in to reply
 

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