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

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

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