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


  • 0
    P
    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.


Log in to reply
 

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