Given N rectangles, check whether they cover a rectangle exactly (with no overlaps).

isBigRect.py

def isBigRect(rectangles):
    if rectangles==[]:
        return True
    L=processBoundaries(rectangles,leftOrRight='left')
    R=processBoundaries(rectangles,leftOrRight='right')
    # print L, R
    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]
    # print 'left', L
    # print 'right', R
    if not L==R:
        return False
    else:
        return True

def processBoundaries(B,leftOrRight='left'):
    if leftOrRight=='right':
        B=[ [x[1][0],[x[0][1],x[1][1]]] for x in B]
        res=[[]]
    elif leftOrRight=='left':
        B=[ [x[0][0],[x[0][1],x[1][1]]] for x in B]
        res=[]
    else:
        print 'process boundaries input error'
        return False
    B.sort(cmp=lambda x,y: x[0]-y[0])
    i=0
    # print 'process B', leftOrRight,B
    while i<len(B):
        x=B[i][0]
        res.append( [x,[]] )
        # print 'process outer while res', i, res
        while i<len(B) and B[i][0]==x:
            res[-1][1].append(B[i][1])
            # print 'process inner while res', i, res
            i=i+1
        res[-1][1]=mergeSpecialIntervals(res[-1][1])
        if res[-1][1]==False:
            return False
    if leftOrRight=='left':
        res.append(['last',res[0][1]])
    else:
        res[0]=['first',res[-1][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])
    # print 'merging',L
    res=[L[0]]
    for i in range(len(L)-1):
        # print 'merge special res',res
        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


A=[[[[0,0],[4,1]],
    [[7,0],[8,2]],
    [[6,2],[8,3]],
    [[5,1],[6,3]],
    [[4,0],[5,1]],
    [[6,0],[7,2]],
    [[4,2],[5,3]],
    [[2,1],[4,3]],
    [[0,1],[2,2]],
    [[0,2],[2,3]],
    [[4,1],[5,2]],
    [[5,0],[6,1]]],

   #shuffled the above a little
   [[[0,0],[4,1]],
    [[7,0],[8,2]],
    [[5,1],[6,3]],
    [[6,0],[7,2]],
    [[4,0],[5,1]],
    [[4,2],[5,3]],
    [[2,1],[4,3]],
    [[0,2],[2,3]],
    [[0,1],[2,2]],
    [[6,2],[8,3]],
    [[5,0],[6,1]],
    [[4,1],[5,2]]],

   [[[0,0],[4,1]]],

   [],

   #vertical stack
   [[[0,0],[1,1]],
	[[0,1],[1,2]],
	[[0,2],[1,3]],
	[[0,3],[1,4]],],
   
   #horizontal stack
   [[[0,0],[1,1]],
	[[1,0],[2,1]],
    [[2,0],[3,1]],
    [[3,0],[4,1]],],

   ]

print 'should be True'
for a in A:
    print isBigRect(a)


B=[
    #missing a square
    [[[0,0],[4,1]],
     [[7,0],[8,2]],
     [[6,2],[8,3]],
     [[5,1],[6,3]],
     [[6,0],[7,2]],
     [[4,2],[5,3]],
     [[2,1],[4,3]],
     [[0,1],[2,2]],
     [[0,2],[2,3]],
     [[4,1],[5,2]],
     [[5,0],[6,1]]],
    
    #exceeds top boundary
    [[[0,0],[4,1]],
     [[7,0],[8,2]],
     [[5,1],[6,4]],
     [[6,0],[7,2]],
     [[4,0],[5,1]],
     [[4,2],[5,3]],
     [[2,1],[4,3]],
     [[0,2],[2,3]],
     [[0,1],[2,2]],
     [[6,2],[8,3]],
     [[5,0],[6,1]],
     [[4,1],[5,2]]],
    
    #two overlapping rectangles
    [[[0,0],[4,1]],
     [[0,0],[4,1]]],
    
    #exceeds right boundary
    [[[0,0],[4,1]],
     [[7,0],[8,3]],
     [[5,1],[6,3]],
     [[6,0],[7,2]],
     [[4,0],[5,1]],
     [[4,2],[5,3]],
     [[2,1],[4,3]],
     [[0,2],[2,3]],
     [[0,1],[2,2]],
     [[6,2],[8,3]],
     [[5,0],[6,1]],
     [[4,1],[5,2]]],

    # has an intersecting pair
    [[[0,0],[5,1]],
     [[7,0],[8,2]],
     [[5,1],[6,3]],
     [[6,0],[7,2]],
     [[4,0],[5,1]],
     [[4,2],[5,3]],
     [[2,1],[4,3]],
     [[0,2],[2,3]],
     [[0,1],[2,2]],
     [[6,2],[8,3]],
     [[5,0],[6,1]],
     [[4,1],[5,2]]],
    
    #skips column 4
    [[[0,0],[4,1]],
     [[7,0],[8,2]],
     [[5,1],[6,3]],
     [[6,0],[7,2]],
     [[2,1],[4,3]],
     [[0,2],[2,3]],
     [[0,1],[2,2]],
     [[6,2],[8,3]],
     [[5,0],[6,1]],],


    #exceed left boundary
    [[[0,0],[4,1]],
     [[7,0],[8,2]],
     [[5,1],[6,3]],
     [[6,0],[7,2]],
     [[4,0],[5,1]],
     [[4,2],[5,3]],
     [[2,1],[4,3]],
     [[-1,2],[2,3]],
     [[0,1],[2,2]],
     [[6,2],[8,3]],
     [[5,0],[6,1]],
     [[4,1],[5,2]]],


   #horizontal stack with overlapping left boundaries at x=1
   [[[0,0],[1,1]],
	[[1,0],[2,1]],
    [[1,0],[3,1]],
    [[3,0],[4,1]],],
]



print 'should be False'
for b in B:
    print isBigRect(b)

A solution for https://discuss.leetcode.com/topic/53781/plane-sweep-to-solve-a-hard-google-onsite-problem-08-10