Perfect Rectangle

题目链接：

扫描线，哪个方向都行。我是从左往右扫，矩阵按照左右的边来存。

首先确定上下的边界，左右线段按照横坐标排序。然后从左往右，如果碰到left的边，就加到集合里，碰到right的边，就从remove掉。

检查重合面积：每次加left的边之前，检查一下集合里面的边是否有和当前left重合的情况，这里集合可以用heap。这里如果横坐标相同先remove right的边，再加left。检查填充满：上图的情况就组成不了一个长方形。那么这时候，每次加进集合的线段是无法填充满up到down的这整条线段的。把横坐标相同的线段按up点排序。每次检查相同x的线段，是否从上到下组成了边界的线段，组成不了就不满足题目要求。每次右边全部remove完的时候记录下横坐标: prev_x，和下一次add的横坐标比较，不相同说明中间有gap。

这道题由于只要找是否重合不需要计算重合的面积和是否有空隙，所以计算相对简单一点。找重合和有空隙只需要把所有横坐标在x的线段排序之后检查首位相连，且起点 = down，终点 = up。这方法超时了，看了discussion的做法，是直接记y轴上线段的长度，然后和up - down比较，这样比较时间就是O(1)了，利用TreeSet来找重合。参考discussion：

public class Solution {    public boolean isRectangleCover(int[][] rectangles) {        // store the rect as left, right lines        List
    
      lines = new ArrayList();        int up = Integer.MIN_VALUE, down = Integer.MAX_VALUE;        for(int[] rect : rectangles) {            // x, down, up, left or right            lines.add(new int[] {rect[0], rect[1], rect[3], -1});            lines.add(new int[] {rect[2], rect[1], rect[3], 1});            up = Math.max(up, rect[3]);            down = Math.min(down, rect[1]);        }        // sort: 1. x, 2. right -> left, 3. down        Collections.sort(lines, (a, b) -> a[0] == b[0] ? (a[3] == b[3] ? a[1] - b[1] : b[3] - a[3]) : a[0] - b[0]);        // 1. non intersection: a.up >= b.down if a.down > b.down        TreeSet
     
       heap = new TreeSet<>((a, b) -> a.up <= b.down ? -1 : (a.down >= b.up ? 1 : 0));        // loop invariant: prev_x = cur_x, cur_x: left line        int i = 0;        int prev_x = lines.get(0)[0];        // length in y        int len = 0;        while(i < lines.size()) {            int cur_x = lines.get(i)[0];            while(i < lines.size() && lines.get(i)[0] == cur_x) {                int[] cur = lines.get(i);                Line line = new Line(cur[1], cur[2]);                // left line                if(cur[3] == -1) {                    // overlap                    if(!heap.add(line)) return false;                    len += line.up - line.down;                }                // right                else {                    heap.remove(line);                    len -= line.up - line.down;                }                i++;            }            if(i != lines.size() && len != up - down) return false;                    }        return true;    }}    class Line {        int up;        int down;        Line(int down, int up) { this.down = down; this.up = up; }        @Override        public int hashCode() {            return this.up * this.down;        }        @Override        public boolean equals(Object a) {            if(a instanceof Line) {                Line b = (Line) a;                return this.up == b.up && this.down == b.down;            }            return false;        }    }
     
    

这题还有个规律，除了四个顶点只出现一次以外，其他所有点都出现两次。且最后成的面积等于小矩形的面积和。

public class Solution {    public boolean isRectangleCover(int[][] rectangles) {        int x1 = Integer.MAX_VALUE, x2 = Integer.MIN_VALUE, y1 = Integer.MAX_VALUE, y2 = Integer.MIN_VALUE;                int area = 0;        Set
    
      set = new HashSet();        for(int[] rect : rectangles) {            area += (rect[2] - rect[0]) * (rect[3] - rect[1]);            x1 = Math.min(x1, rect[0]);            y1 = Math.min(y1, rect[1]);            x2 = Math.max(x2, rect[2]);            y2 = Math.max(y2, rect[3]);                        String s1 = rect[0] + " " + rect[1];            String s2 = rect[0] + " " + rect[3];            String s3 = rect[2] + " " + rect[1];            String s4 = rect[2] + " " + rect[3];                        if(!set.add(s1)) set.remove(s1);            if(!set.add(s2)) set.remove(s2);            if(!set.add(s3)) set.remove(s3);            if(!set.add(s4)) set.remove(s4);        }        // condition 1        if(area != (x2 - x1) * (y2 - y1)) return false;                // condition 2        return set.contains(x1 + " " + y1) && set.contains(x1 + " " + y2) && set.contains(x2 + " " + y1) && set.contains(x2 + " " + y2) && set.size() == 4;            }}