Python binary search like merge interval, okay I do not have a handy treeset

• ``````class Solution(object):
def isRectangleCover(self, rectangles):
"""
:type rectangles: List[List[int]]
:rtype: bool
"""
rectangles.sort(key=lambda x:x[1])
rectangles.sort(key=lambda x:x[0])
bottom, left = rectangles[0][0], rectangles[0][1]
# left, right, height
row = []
i = 0
while i < len(rectangles) and rectangles[i][0] == bottom:
# right boundary matches left boundary
if not row or row[-1][1] == rectangles[i][1]:
# different height
if not row or row[-1][2] != rectangles[i][2]:
row.append([rectangles[i][1], rectangles[i][3], rectangles[i][2]])
else:
row[-1][1] = rectangles[i][3]
else:
return False
i += 1
right = row[-1][1]

def binarySearch(x):
l, r = 0, len(row) - 1
while l + 1 < r:
mid = (l + r) / 2
if row[mid][0] >= x:
r = mid
else:
l = mid
if row[r][0] <= x:
return r
else:
return l

while i < len(rectangles):
# exceeds left or right boundary
if rectangles[i][1] < left or rectangles[i][3] > right:
return False
pos = binarySearch(rectangles[i][1])
# does not match rectangle under it or out of under rectangle's range
if rectangles[i][0] != row[pos][2] or rectangles[i][3] > row[pos][1]:
return False
# left and rght boundary match under rectangle
if rectangles[i][1] == row[pos][0] and rectangles[i][3] == row[pos][1]:
row[pos][2] = rectangles[i][2]
# merge
if pos < len(row) - 1 and row[pos + 1][2] == row[pos][2]:
row[pos][1] = row[pos + 1][1]
del row[pos + 1]
if pos > 0 and row[pos - 1][2] == row[pos][2]:
row[pos][0] = row[pos - 1][0]
del row[pos - 1]
# left boundary match
elif rectangles[i][1] == row[pos][0]:
# merge
if pos > 0 and row[pos - 1][2] == rectangles[i][2]:
row[pos - 1][1] = rectangles[i][3]
row[pos][0] = rectangles[i][3]
else:
row[pos][0] = rectangles[i][3]
row.insert(pos, [rectangles[i][1], rectangles[i][3], rectangles[i][2]])
# right boundary match
elif rectangles[i][3] == row[pos][1]:
# merge
if pos < len(row) - 1 and row[pos + 1][2] == rectangles[i][2]:
row[pos + 1][0] = rectangles[i][1]
row[pos][1] = rectangles[i][1]
else:
row[pos][1] = rectangles[i][1]
row.insert(pos + 1, [rectangles[i][1], rectangles[i][3], rectangles[i][2]])
# smaller
else:
row.insert(pos, row[pos])
row[pos][1] = rectangles[i][1]
row[pos + 1][0] = rectangles[i][3]
row.insert(pos + 1, [rectangles[i][1], rectangles[i][3], rectangles[i][2]])
i += 1
return len(row) == 1
``````

The idea is similar to merge interval. Except that you have to consider both x and y.

1.I sort rectangles by y and x coordinates (bottom left). So smaller x comes first, if x is the same, smaller y comes first. In this case, whenever you have a rectangle to put, you are guaranteed that the rectangle under it and the rectangle before it should be put already.
row is used to record histogram-like ranges. left, right and height.
2.Put the bottom rectangles first to get the left and right boundary. Everytime check whether last right boundary matches current left boundary.
3.Then you start to put top rectangles. If the rectangle is out of left or right boundary or does not match the height of its left and right boundaries in row, return False. Otherwise, 4 cases described above and do put and merge accordingly.

If finally you get one histogram-like item in row. You get the rectangle.

Long code, I know. I like inner function. Help me shrink it.

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