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

題目鏈接：https://leetcode.com/problems...

掃描線，哪個(gè)方向都行。我是從左往右掃，矩陣按照左右的邊來(lái)存。

首先確定上下的邊界，左右線段按照橫坐標(biāo)排序。然后從左往右，如果碰到left的邊，就加到集合里，碰到right的邊，就從remove掉。
檢查重合面積：每次加left的邊之前，檢查一下集合里面的邊是否有和當(dāng)前l(fā)eft重合的情況，這里集合可以用heap。這里如果橫坐標(biāo)相同先remove right的邊，再加left。
檢查填充滿：上圖的情況就組成不了一個(gè)長(zhǎng)方形。那么這時(shí)候，每次加進(jìn)集合的線段是無(wú)法填充滿up到down的這整條線段的。把橫坐標(biāo)相同的線段按up點(diǎn)排序。每次檢查相同x的線段，是否從上到下組成了邊界的線段，組成不了就不滿足題目要求。每次右邊全部remove完的時(shí)候記錄下橫坐標(biāo): prev_x，和下一次add的橫坐標(biāo)比較，不相同說(shuō)明中間有g(shù)ap。

這道題由于只要找是否重合不需要計(jì)算重合的面積和是否有空隙，所以計(jì)算相對(duì)簡(jiǎn)單一點(diǎn)。找重合和有空隙只需要把所有橫坐標(biāo)在x的線段排序之后檢查首位相連，且起點(diǎn) = down，終點(diǎn) = up。這方法超時(shí)了，看了discussion的做法，是直接記y軸上線段的長(zhǎng)度，然后和up - down比較，這樣比較時(shí)間就是O(1)了，利用TreeSet來(lái)找重合。參考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;
        }
    }

這題還有個(gè)規(guī)律，除了四個(gè)頂點(diǎn)只出現(xiàn)一次以外，其他所有點(diǎn)都出現(xiàn)兩次。且最后成的面積等于小矩形的面積和。
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;
        
    }
}