391 Perfect Rectangle

391. Perfect Rectangle

1. Question

Given N axis-aligned rectangles where N > 0, determine if they all together form an exact cover of a rectangular region.

Each rectangle is represented as a bottom-left point and a top-right point. For example, a unit square is represented as [1,1,2,2]. (coordinate of bottom-left point is (1, 1) and top-right point is (2, 2)).

Example 1:

rectangles = [
  [1,1,3,3],
  [3,1,4,2],
  [3,2,4,4],
  [1,3,2,4],
  [2,3,3,4]
]

Return true. All 5 rectangles together form an exact cover of a rectangular region.

Example 2:

rectangles = [
  [1,1,2,3],
  [1,3,2,4],
  [3,1,4,2],
  [3,2,4,4]
]

Return false. Because there is a gap between the two rectangular regions.

Example 3:

rectangles = [
  [1,1,3,3],
  [3,1,4,2],
  [1,3,2,4],
  [3,2,4,4]
]
Return false. Because there is a gap in the top center.

Example 4:

rectangles = [
  [1,1,3,3],
  [3,1,4,2],
  [1,3,2,4],
  [2,2,4,4]
]

Return false. Because two of the rectangles overlap with each other.

2. Implementation

(1) Scan Line + Heap + TreeSet

思路:

1.首先我们定义一个Rectangle的类，其中包含对应的其属于rectangle的所有点的信息，以及这个rectangle的x是一个矩阵的左x还是右x这些信息。将每个点离散化，将左边和右边的x值分别定义一个Rectangle类，放在一个最小堆里

2.第二步，我们用一个TreeSet保存每个rectangle关于y点的信息，按照y值从小到大排序。这里对set的comparator，我们用了小技巧，如果两个rectangle的y interval相交，compare函数会返回0，这样当我们call set.add()的时候，set.add会返回0。

3.最后一步则是按照x的值从小到大的顺序，分别处理其对应矩阵的y interval，判断每个x点对应的y interval是否存在overlap或者gap,如果有则返回false

class Solution {
    public boolean isRectangleCover(int[][] rectangles) {
        if (rectangles == null || rectangles.length == 0) {
            return false;
        }

        int top = Integer.MIN_VALUE, bottom = Integer.MAX_VALUE;
        PriorityQueue<Rectangle> minHeap = new PriorityQueue();

        // Sort points in ascending order based on x-interval, and find the max value and min value of y 
        for (int[] rectangle : rectangles) {
            minHeap.add(new Rectangle(rectangle[0], rectangle, false));
            minHeap.add(new Rectangle(rectangle[2], rectangle, true));
            top = Math.max(top, rectangle[3]);
            bottom = Math.min(bottom, rectangle[1]);
        }

        // Sort points in ascending order based on y-interval
        Set<int[]> set = new TreeSet(new Comparator<int[]>(){
            @Override
            public int compare(int[] p1, int[] p2) {
                if (p1[3] <= p2[1]) {
                    return -1;
                }
                else if (p1[1] >= p2[3]) {
                    return 1;
                }
                // There is an intersection in the y-interval, return 0 in TreeSet and set.add() will return false;
                else {
                    return 0;
                }
            }
        });

        int y_interval = 0;
        while (!minHeap.isEmpty()) {
            int x = minHeap.peek().x;
            // Handle the edge vertically
            while (!minHeap.isEmpty() && x == minHeap.peek().x) {
                Rectangle rect = minHeap.remove();
                int[] points = rect.points;

                if (rect.isEnd) {
                    set.remove(points);
                    y_interval -= points[3] - points[1];
                }
                else {
                    // Found intersection in y_interval, cannot get perfect rectangle
                    if (!set.add(points)) {
                        return false;
                    }
                    y_interval += points[3] - points[1];
                }
            }

            // For perfect rectangle, the y_interval must be equal to the difference betwee top and bottom
            // Otherwise, it means there is a vertical gap between rectangles
            if (!minHeap.isEmpty() && (y_interval != (top - bottom))) {
                return false;
            }
        }
        return true;
    }

    class Rectangle implements Comparable<Rectangle>{
        int x;
        int[] points;
        boolean isEnd;

        public Rectangle(int x, int[] points, boolean isEnd) {
            this.x = x;
            this.points = points;
            this.isEnd = isEnd;
        }

        // When there is an intersection for two rectangle at x, the rectangle with a smaller bottom left x should comes before the other 
        public int compareTo(Rectangle that) {
            return this.x == that.x ? this.points[0] - that.points[0] : this.x - that.x;
        }
    }
}

(2) HashSet

思路: 通过观察，我们发现如果所有矩形可以组成perfect rectangle,那么perfect rectangle的四个顶点必须只出现一次，其他地点出现偶数次，同时perfect rectangle的面积等于所有矩形的面积之和

class Solution {
    public boolean isRectangleCover(int[][] rectangles) {
        if (rectangles == null || rectangles.length == 0) {
            return false;
        }

        int x1 = Integer.MAX_VALUE;
        int x2 = Integer.MIN_VALUE;
        int y1 = Integer.MAX_VALUE;
        int y2 = Integer.MIN_VALUE;

        Set<String> set = new HashSet<>();
        int area = 0;

        for (int[] rectangle : rectangles) {
            x1 = Math.min(x1, rectangle[0]);
            x2 = Math.max(x2, rectangle[2]);
            y1 = Math.min(y1, rectangle[1]);
            y2 = Math.max(y2, rectangle[3]);

            area += (rectangle[2] - rectangle[0]) * (rectangle[3] - rectangle[1]);

            String code1 = rectangle[0] + "#" + rectangle[1];
            String code2 = rectangle[0] + "#" + rectangle[3];
            String code3 = rectangle[2] + "#" + rectangle[1];
            String code4 = rectangle[2] + "#" + rectangle[3];

            if (!set.add(code1)) set.remove(code1);
            if (!set.add(code2)) set.remove(code2);
            if (!set.add(code3)) set.remove(code3);
            if (!set.add(code4)) set.remove(code4);
        }

        if (set.size() != 4 || !set.contains(x1 + "#" + y1) || !set.contains(x1 + "#" + y2) 
            || !set.contains(x2 + "#" + y1) || !set.contains(x2 + "#" + y2)) {
            return false;
        }
        return area == (x2 - x1) * (y2 - y1);
    }
}

3. Time & Space Complexity

Scan Line + Heap + TreeSet: 时间复杂度O(nlogn), n是rectangle的个数, 空间复杂度O(n)

HashSet: 时间复杂度O(n), 空间复杂度O(n)