Given an array rectangles where rectangles[i] = [xi, yi, ai, bi] represents an axis-aligned rectangle. The bottom-left point of the rectangle is (xi, yi) and the top-right point of it is (ai, bi).

Return true if all the rectangles together form an exact cover of a rectangular region.

&nbsp;
Example 1:

Input: rectangles = [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]
Output: true
Explanation: All 5 rectangles together form an exact cover of a rectangular region.


Example 2:

Input: rectangles = [[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]
Output: false
Explanation: Because there is a gap between the two rectangular regions.


Example 3:

Input: rectangles = [[1,1,3,3],[3,1,4,2],[1,3,2,4],[2,2,4,4]]
Output: false
Explanation: Because two of the rectangles overlap with each other.


&nbsp;
Constraints:


	1 &lt;= rectangles.length &lt;= 2 * 104
	rectangles[i].length == 4
	-105 &lt;= xi, yi, ai, bi &lt;= 105


class Solution:
    def isRectangleCover(self, rectangles: List[List[int]]) -> bool:
        X1, Y1 = float('inf'), float('inf')
        X2, Y2 = -float('inf'), -float('inf')

        points = set()
        actual_area = 0
        for x1, y1, x2, y2 in rectangles:
            # calculate the coords of the potential perfect rectangle
            X1, Y1 = min(X1, x1), min(Y1, y1)
            X2, Y2 = max(X2, x2), max(Y2, y2)
            # add up to the actual_area, so we can check against to see if thers is any part overwritten.
            actual_area += (x2 - x1) * (y2 - y1)
            
            # proving steps in https://labuladong.github.io/algo/4/32/131/
            for p in [(x1, y1), (x1, y2), (x2, y1), (x2, y2)]:
                if p in points: 
                    points.remove(p)
                else:           
                    points.add(p)

        # check the area 
        expected_area = (X2 - X1) * (Y2 - Y1)
        if actual_area != expected_area:
            return False
        
        if len(points) != 4:       
            return False

        if (X1, Y1) not in points: 
            return False
        if (X1, Y2) not in points: 
            return False
        if (X2, Y1) not in points: 
            return False
        if (X2, Y2) not in points: 
            return False

        return True
class Solution {
    // Rectangle x0,y0,x1,y1
    public boolean isRectangleCover(int[][] rectangles) {
        // Ordered by y0 first and x0 second
        Arrays.sort(rectangles,(r1,r2)->{
           if(r1[1]==r2[1]) return r1[0]-r2[0];
            return r1[1]-r2[1];
        });

        // Layering rectangles with pq, ordered by y1 first and x0 second
        PriorityQueue<int[]> pq = new PriorityQueue<>((r1,r2)->{
            if(r1[3]==r2[3]) return r1[0]-r2[0];
            return r1[3]-r2[3];
        });

        // Create first layer
        pq.offer(rectangles[0]);
        int i=1;
        while(i<rectangles.length&&rectangles[i][1]==rectangles[i-1][1]){
            if(rectangles[i][0]!=rectangles[i-1][2]) return false;
            pq.offer(rectangles[i++]);
        }

        while(i<rectangles.length){
            int[] curr = rectangles[i++];
            int x=curr[0];
            //matching current rectangle with rectangles in the lower layer
            while(!pq.isEmpty()&&x<curr[2]){
                int[] prev=pq.poll();
                if(prev[3]!=curr[1]||prev[0]!=x) return false;
                if(prev[2]>curr[2]){
                    pq.offer(new int[]{curr[2], prev[1], prev[2], prev[3]});
                    x=curr[2];
                }else {
                    x=prev[2];
                }
            }
            if(x<curr[2]) return false;
            pq.offer(curr);
        }

        int[] prev=pq.poll();
        while(!pq.isEmpty()){
            if(pq.poll()[3]!=prev[3]) return false;
        }

        return true;
    }
}
class Solution {
 public:
  bool isRectangleCover(vector<vector<int>>& rectangles) {
    SegmentTree<STMax> st(2e5 + 1);
    sort(rectangles.begin(), rectangles.end(), [](auto& lhs, auto& rhs) -> bool {
      if (lhs[1] != rhs[1]) return lhs[1] < rhs[1];
      return lhs[0] < rhs[0];
    });

    int min_x = rectangles[0][0];
    int min_y = rectangles[0][1];
    int max_a = rectangles[0][2];
    int max_b = rectangles[0][3];
    long long sum = 1ll * (max_a - min_x) * (max_b - min_y);
    st.update(min_x + 1e5 + 1, max_a + 1e5, max_b);
    for (int i = 1; i < rectangles.size(); ++i) {
      if (rectangles[i][0] < min_x) return false;
      int max_height = st.query(rectangles[i][0] + 1e5 + 1, rectangles[i][2] + 1e5);
      if (max_height > rectangles[i][1]) return false;
      max_a = max(max_a, rectangles[i][2]);
      max_b = max(max_b, rectangles[i][3]);
      sum += 1ll * (rectangles[i][2] - rectangles[i][0]) * (rectangles[i][3] - rectangles[i][1]);
      st.update(rectangles[i][0] + 1e5 + 1, rectangles[i][2] + 1e5, rectangles[i][3]);
    }
    return sum == 1ll * (max_a - min_x) * (max_b - min_y);
  }
};
var isRectangleCover = function(R) {
    // left to right, bottom to top (so sort on bottom first, then left)
    R.sort(([left1, bottom1], [left2, bottom2]) => bottom1 - bottom2 || left1 - left2);

    // Find all corners
    let leftMost = Infinity,
        bottomMost = Infinity,
        rightMost = -Infinity,
        topMost = -Infinity;
    for (let [left, bottom, right, top] of R) {
        leftMost = Math.min(leftMost, left);
        bottomMost = Math.min(bottomMost, bottom);
        rightMost = Math.max(rightMost, right);
        topMost = Math.max(topMost, top);
    }

    // All calculations are with-respect-to large rectangle
    let CH = new Array(rightMost - leftMost).fill(0);
    for (let [left, bottom, right, top] of R) {
        const baseHeight = bottom - bottomMost; // how high base is
        const ceilHeight = top - bottomMost; // how high ceil is
        for (let tempLeft = left; tempLeft < right; tempLeft++) {
            if (CH[tempLeft - leftMost] != baseHeight)
                return false; // > is a duplicate cell < is a gap/ missing cell/ hole
            CH[tempLeft - leftMost] = ceilHeight;
        }
    }

    const rectHeight = topMost - bottomMost;
    for (let ceilHeight of CH) {
        if (ceilHeight !== rectHeight)
            return false;
    }
    return true;
}
Perfect Rectangle