Python sweep line solution using bisect


  • 0
    T
    def isRectangleCover(self, rectangles):
        area = 0
        minx,miny = sys.maxint,sys.maxint
        maxx,maxy = -sys.maxint,-sys.maxint
        vertical = []
        for x1,y1,x2,y2 in rectangles:
            minx,miny = min(x1,minx), min(y1,miny)
            maxx,maxy = max(x2,maxx), max(y2,maxy)
            area += (y2-y1)*(x2-x1)
            vertical.append((x1,1,y1,y2))
            vertical.append((x2,-1,y1,y2))
        if area != (maxx-minx)*(maxy-miny):
            return False
        e = []
        vertical.sort()
        for x,t,y1,y2 in vertical:
            if t > 0:
                i = bisect.bisect_left(e,(y1,y2))
                bisect.insort_left(e,(y1,y2))
                if i+1<len(e) and e[i][1]>e[i+1][0] or i>0 and e[i][0]<e[i-1][1]: return False
            else:
                e.remove((y1,y2))
        return True

  • 0

    This is the best what Python can do. I upvoted it.


Log in to reply
 

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