Perfect Rectangle

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<int[]> 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<Line> 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<String> 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;
        
    }
}