I blogged about this before it was a LeetCode question. Nice to see it here! O(nlog n) solution with explanation


  • 0
    A

    I solved this in a blog post after seeing it in the LeetCode forums but before it was posted as a LeetCode question. I'm very pleased to see that there are O(n) solutions!

    Here is my explanation and code.

    http://alejandroerickson.com/j/2016/08/14/determine-if-n-given-rectangles-are-an-exact-cover-of-a-rectangle.html

    def isBigRect(rectangles):
        if rectangles==[]:
            return True
        L=processBoundaries(rectangles,leftOrRight='left')
        R=processBoundaries(rectangles,leftOrRight='right')
        if L==False or R==False or not len(L)==len(R):
            return False
        L[-1][0]=R[-1][0]
        R[0][0]=L[0][0]
        if not L==R:
            return False
        else:
            return True
    
    def processBoundaries(B,leftOrRight='left'):
        x0orx1=0
        if leftOrRight=='right':
            x0orx1=1
            res=[[]]
        elif leftOrRight=='left':
            x0orx1=0
            res=[]
        else:
            print 'process boundaries input error'
            return False
        B=[ [x[x0orx1][0],[x[0][1],x[1][1]]] for x in B]
        B.sort(cmp=lambda x,y: x[0]-y[0])
        i=0
        while i<len(B):
            x=B[i][0]
            res.append( [x,[]] )
            while i<len(B) and B[i][0]==x:
                res[-1][1].append(B[i][1])
                i=i+1
            res[-1][1]=mergeSpecialIntervals(res[-1][1])
            if res[-1][1]==False:
                return False
        if leftOrRight=='right':
            res[0]=['first',res[-1][1]]
        else:
            res.append(['last',res[0][1]])
        return res
    
    def mergeSpecialIntervals(L):
        if L==[]:
            return False
        if len(L)==1:
            return L
        L.sort(cmp=lambda x,y: x[0]-y[0])
        res=[L[0]]
        for i in range(len(L)-1):
            if L[i][1]>L[i+1][0]:
                return False
            elif L[i][1]==L[i+1][0]:
                res[-1][1]=L[i+1][1]
                i=i+2
            else:
                res.append(L[i])
                i=i+1
        if i == len(L)-1:
            res.append(L[i])
        return res
    

Log in to reply
 

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