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

• 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
``````

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