摘要：首先確定上下的邊界，左右線段按照橫坐標排序。檢查填充滿上圖的情況就組成不了一個長方形。找重合和有空隙只需要把所有橫坐標在的線段排序之后檢查首位相連，且起點，終點。且最后成的面積等于小矩形的面積和。

題目鏈接：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;
        
    }
}