Perfect Rectangle

摘要：首先确定上下的边界，左右线段按照横坐标排序。检查填充满上图的情况就组成不了一个长方形。找重合和有空隙只需要把所有横坐标在的线段排序之后检查首位相连，且起点，终点。且最后成的面积等于小矩形的面积和。

题目链接：https://leetcode.com/problems...

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

首先确定上下的边界，左右线段按照横坐标排序。然后从左往右，如果碰到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：
https://discuss.leetcode.com/...

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;
        }
    }

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

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;
        
    }
}