Python O(n log(n)) Segmented Boundary Line Solution


  • 0
    L

    The rectangles are sorted first - thus O(n log(n)).

    Each rectangle updates the segmented boundary line of rectangles seen so far. The boundary line starts with a single vertical line from bottom-left to top-left. If at the end the line has a single segment the covering succeeds.

    For each rectangle:
    a) cut out its left side from the boundary line
    b) merge the right side with the boundary line

    Each line segment [(x, y1), (x, y2)] is stored in two dictionaries: ends[x, y1]=y2 and begs[x, y2]=y1.

    class Solution(object):
        def isRectangleCover(self, rectangles):
            """
            :type rectangles: List[List[int]]
            :rtype: bool
            """
            rects = sorted(rectangles)
            # Maintain a segmented line - the boundary of processed rectangles.
            # Each segment is stored in two dictionaries - begs and ends.
            # Start with a single segment from bottom to top on the left.
            x = rects[0][0]
            a = min(r[1] for r in rects)
            b = max(r[3] for r in rects)
            ends = {(x, a): b}
            begs = {(x, b): a}
            for x1, y1, x2, y2 in rects:
                # Cut out the bottom of the rectangle from the line.
                b = ends.pop((x1, y1), None)
                if b == None or b < y2: return False
                if b == y2:
                    begs.pop((x1, b))
                else:
                    ends[(x1, y2)] = b
                    begs[(x1, b)] = y2
                # Merge the top of the rectangle with the line.
                a = begs.pop((x2, y1), None)
                b = ends.pop((x2, y2), None)
                if a == None: a = y1
                if b == None: b = y2
                ends[(x2, a)] = b
                begs[(x2, b)] = a
            # A single segment at the end is success.
            return len(ends) == 1
    

Log in to reply
 

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