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:
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 > l2: l1, l2 = l2, l1 return l2 < l1 def judgeOverlap(self, rec1, rec2): vl1, vl2, hl1, hl2 = [rec1, rec1], [rec2, rec2], [rec1, rec1], [rec2, rec2] 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 - rec) * (rec - rec) lm, rm, um, dm = min(lm, rec), max(rm, rec), max(um, rec), min(dm, rec) 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.
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 pointset.add((leftbottom, leftbottom)) for i in xrange(len(rectangles)): rec = rectangles[i] area += (rec - rec) * (rec - rec) lm, rm, um, dm = min(lm, rec), max(rm, rec), max(um, rec), min(dm, rec) if not (rec, rec) in pointset or (i != 0 and rec == rectangles[i - 1]): return False pointset.add((rec, rec)) pointset.add((rec, rec)) return area == (um - dm) * (rm - lm) and (rm, dm) in pointset