Problem statement

https://leetcode.com/problems/perfect-rectangle/

Solution

The idea is to use line sweep method: we use vertical line and move it from left to right and we need to check two condition holds:

  1. That sum of areas of rectangles is equal to area of the rectangle [min_x, min_y, max_x, max_y], where these 4 points are the most left, bottom, right and top points.
  2. That each time we add or remove segment from our active set, we do not have intersections. Note, that we do not need to check that they fully cover all range, condition 1 will be enough.

So, we create events: for start rectangle event we use signature (x1, 1, y1, y2) and for end rectangle we use (x2, -1, y1, y2). Then we sort events and run our line sweep approach:

  1. If beg_end > 0, that is equal to 1, it means that we need to add new interval: (y1, y2). We add it and then check that we do not have itersection with previous or next intervals. If we have, return False immedietly. Here we keep SortedList to quickly add and remove intervals.
  2. If we have beg_end == -1, then we just remove interval from our active set.

Complexity

It is O(n*log n), because on each level we have O(log n) complexity. If we used not sortedcontainers, but usual list + insort, complexity would have been O(n^2), but in practice it works just a bit slower due to not very strict constraints.

Code

from sortedcontainers import SortedList

class Solution:
    def isRectangleCover(self, R):
        min_x = min(a[0] for a in R)
        min_y = min(a[1] for a in R)
        max_x = max(a[2] for a in R)
        max_y = max(a[3] for a in R)
        if (max_x-min_x)*(max_y-min_y)!= sum((y2-y1)*(x2-x1) for x1,y1,x2,y2 in R):
            return False
        
        vertical = []
        for x1, y1, x2, y2 in R:
            vertical.append((x1, 1, y1, y2))
            vertical.append((x2,-1, y1, y2))
        vertical.sort()
        
        line = SortedList()
        
        for _, beg_end, y1, y2 in vertical:
            if beg_end > 0:
                i = line.bisect((y1, y2))
                line.add((y1, y2))
                if i + 1 < len(line) and line[i][1] > line[i+1][0]: return False
                if i > 0 and line[i][0] < line[i-1][1]: return False   
            else:
                line.remove((y1, y2))

        return True

Remark

Note, that there is also mathematical O(n) solution, with the following idea:

  1. First condition is the same: sum of areas must be equal to area of big rectangle.
  2. Each point should be here 2 or 4 times, except 4 corners, which should be here exactly 1 time.

It is nice and clean solution, however in my opinion it is quite difficult to invent it.