Monday, August 29, 2016

LeetCode 391 - Perfect Rectangle


http://bookshadow.com/weblog/2016/08/28/leetcode-perfect-rectangle/
Given N axis-aligned rectangles where N > 0, determine if they all together form an exact cover of a rectangular region.
Each rectangle is represented as a bottom-left point and a top-right point. For example, a unit square is represented as [1,1,2,2]. (coordinate of bottom-left point is (1, 1) and top-right point is (2, 2)).
Example 1:
rectangles = [
  [1,1,3,3],
  [3,1,4,2],
  [3,2,4,4],
  [1,3,2,4],
  [2,3,3,4]
]

Return true. All 5 rectangles together form an exact cover of a rectangular region.
Example 2:
rectangles = [
  [1,1,2,3],
  [1,3,2,4],
  [3,1,4,2],
  [3,2,4,4]
]

Return false. Because there is a gap between the two rectangular regions.
Example 3:
rectangles = [
  [1,1,3,3],
  [3,1,4,2],
  [1,3,2,4],
  [3,2,4,4]
]

Return false. Because there is a gap in the top center.
Example 4:



rectangles = [
  [1,1,3,3],
  [3,1,4,2],
  [1,3,2,4],
  [2,2,4,4]
]

Return false. Because two of the rectangles overlap with each other.
If all rectangles can form an exact rectangular area, they should follow these conditions:
  1. The sum of area of all small rectangles should equal to the area of large rectangle.
  2. At any position except outer four corners, the amount of overlapping corners should be even (2, 4).
  3. Corners that overlap at the same point should be different type (top-left, top-right, bottom-left, bottom-right).
So, I used
  1. Four int variables to record the boundaries of large rectangle and then calculate the area.
  2. A hashmap that maps corner with its type.
  3. Four numbers (1, 2, 4, 8) to represent four types of corner. Then use bit manipulation to modify and check.
O(n) time complexity, O(n) space, 112 ms run time.
    Map<String, Integer> map = new HashMap<String, Integer>();
    public boolean isRectangleCover(int[][] rectangles) {
        if (rectangles.length == 0 || rectangles[0].length == 0) return false;
        int lx = Integer.MAX_VALUE, ly = lx, rx = Integer.MIN_VALUE, ry = rx, sum = 0;
        for (int[] rec : rectangles) {
            lx = Math.min(lx, rec[0]);
            ly = Math.min(ly, rec[1]);
            rx = Math.max(rx, rec[2]);
            ry = Math.max(ry, rec[3]);
            sum += (rec[2] - rec[0]) * (rec[3] - rec[1]);
            //bottom-left
            if (overlap(rec[0] + " " + rec[1], 1)) return false;
            //top-left
            if (overlap(rec[0] + " " + rec[3], 2)) return false;
            //bottom-right
            if (overlap(rec[2] + " " + rec[1], 4)) return false;
            //top-right
            if (overlap(rec[2] + " " + rec[3], 8)) return false;
        }
        int count = 0;
        Iterator<Integer> iter = map.values().iterator();
        while (iter.hasNext()) {
            Integer i = iter.next();
            if (i != 15 && i != 12 && i != 10 && i != 9 && i != 6 && i != 5 && i != 3) count++;
        }
        return count == 4 && sum == (rx - lx) * (ry - ly);
    }
    
    private boolean overlap(String corner, Integer type) {
        Integer temp = map.get(corner);
        if (temp == null) temp = type;
        else if ((temp & type) != 0) return true;
        else temp |= type;
        map.put(corner, temp);
        return false;
    }
参考LeetCode Discuss:https://discuss.leetcode.com/topic/55870/share-my-solutions-for-contest-2/2
首先求出所有矩形中横纵坐标的最小/最大值,记为left, right, bottom, top

遍历rectangles,记当前矩形为rect,其左、下、右、上坐标分别为l, b, r, t,则矩形的宽度w = r - l;高度h = t - b

利用数组heights记录矩形左、右边界的高度:

heights[l] += h

heights[r] -= h

利用数组widths记录矩形下、上边界的宽度:

widths[b] += w

widths[t] -= w

从left至right遍历一遍heights数组,检查相邻的height是否相等,并进行累加

从bottom至top遍历一遍widths数组,检查相邻的width是否相等,并进行累加

最后检查上述两个步骤的累加值是否等于(top - bottom) * (right - left)

def isRectangleCover(self, rectangles): """ :type rectangles: List[List[int]] :rtype: bool """ left = min(x[0] for x in rectangles) bottom = min(x[1] for x in rectangles) right = max(x[2] for x in rectangles) top = max(x[3] for x in rectangles) heights = collections.defaultdict(int) widths = collections.defaultdict(int) for rect in rectangles: l, b, r, t = rect h, w = t - b, r - l heights[l] += h heights[r] -= h widths[b] += w widths[t] -= w hSum = heights[left] for x in range(left + 1, right): heights[x] += heights[x - 1] if heights[x] != heights[x - 1]: return False hSum += heights[x] wSum = widths[bottom] for x in range(bottom + 1, top): widths[x] += widths[x - 1] if widths[x] != widths[x - 1]: return False wSum += widths[x] return hSum == wSum == (top - bottom) * (right - left)

https://discuss.leetcode.com/topic/56052/really-easy-understanding-solution-o-n-java
The right answer must satisfy two conditions:
  1. the large rectangle area should be equal to the sum of small rectangles
  2. count of all the points should be even, and that of all the four corner points should be one
For those who are concerned with the validity of the two conditions, here is a quick proof.
Proof to condition 1 is straightforward so I will focus on condition 2. First by observation we know it holds true for a perfect rectangle (consider how many small rectangles can overlap at a particular point: the number has to be even except for the four corner points of the prefect rectangle). The real question is whether it can also be true for some non-perfect rectangle.
Let's begin with the question: what will a non-perfect rectangle look like? Of course it can look like rather complicated but here is a simple way to define it: any non-perfect rectangle can be obtained by a sequence of adding or removing rectangular parts from its perfect counterpart (the order for adding or removing does not matter here). If condition 1 is held true, the non-perfect rectangle must be built by both adding and removing small rectangles such that the total area of added rectangles compensates those of removed.
Without loss of generality, let's focus on the first rectangle (denoted as FR) that is being removed (i.e., we have perfect rectangle before removing it). FR has four corner points. Before removing it, each corner points will appear even times. After it's gone, all the four corner points will appear odd times. To make condition 2 hold true, for each of these four points, we have to either add or remove a rectangle such that each of them will once again appear even times. The key here is that the total number of rectangles added or removed is at least two, since the added or removed rectangles cannot overlap with FR, therefore each added or removed rectangle can contain at most two of the four corner points of FR.
Now we have at least two extra rectangles (either added or removed), with a total of eight corner points. Four of those points coincide with the four corner points of FR. What about the other four points? For each of these points, if it belongs to a rectangle that is being removed, then before removing, it must appear even times and after removing, it will appear odd times. If it belongs to a rectangle that is being added, depending on whether it coincides with any point in the perfect rectangle, its number of appearance will still be odd (appear once if does not coincide with any point, odd if it does since the original number of appearance before adding is even). In either case (adding or removing rectangle), there is no way to keep the number of appearance of all points even, therefore condition 2 cannot be true for non-perfect rectangles.
I think this is a flavor of the Packing Problem which I believe what applications are using (for example) to fit horizontal and vertical photos side by side on your rectangle phone
public boolean isRectangleCover(int[][] rectangles) {

        if (rectangles.length == 0 || rectangles[0].length == 0) return false;

        int x1 = Integer.MAX_VALUE;
        int x2 = Integer.MIN_VALUE;
        int y1 = Integer.MAX_VALUE;
        int y2 = Integer.MIN_VALUE;
        
        HashSet<String> set = new HashSet<String>();
        int area = 0;
        
        for (int[] rect : rectangles) {
            x1 = Math.min(rect[0], x1);
            y1 = Math.min(rect[1], y1);
            x2 = Math.max(rect[2], x2);
            y2 = Math.max(rect[3], y2);
            
            area += (rect[2] - rect[0]) * (rect[3] - rect[1]);
            
            String s1 = rect[0] + " " + rect[1];
            String s2 = rect[0] + " " + rect[3];
            String s3 = rect[2] + " " + rect[3];
            String s4 = rect[2] + " " + rect[1];
            
            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);
        }
        
        if (!set.contains(x1 + " " + y1) || !set.contains(x1 + " " + y2) || !set.contains(x2 + " " + y1) || !set.contains(x2 + " " + y2) || set.size() != 4) return false;
        
        return area == (x2-x1) * (y2-y1);
    }
http://blog.csdn.net/mebiuw/article/details/52354018
* 核心思想就是:能够正好围成一个矩形的情况就是: * 有且只有: * - 最左下 最左上 最右下 最右上 的四个点只出现过一次,其他肯定是成对出现的(保证完全覆盖) * - 上面四个点围成的面积,正好等于所有子矩形的面积之和(保证不重复)

public boolean isRectangleCover(int[][] rectangles) { int left = Integer.MAX_VALUE; int right = Integer.MIN_VALUE; int top = Integer.MIN_VALUE; int bottom = Integer.MAX_VALUE; int n = rectangles.length; HashSet<String> flags = new HashSet<String>(); int totalArea = 0; for(int i=0;i<n;i++){ left = Math.min(left,rectangles[i][0]); bottom = Math.min(bottom,rectangles[i][1]); right = Math.max(right,rectangles[i][2]); top = Math.max(top,rectangles[i][3]); totalArea += (rectangles[i][3]-rectangles[i][1])*(rectangles[i][2]-rectangles[i][0]); String pointLT = rectangles[i][0] + " "+ rectangles[i][3]; String pointLB = rectangles[i][0] + " "+ rectangles[i][1]; String pointRT = rectangles[i][2] + " "+ rectangles[i][3]; String pointRB = rectangles[i][2] + " "+ rectangles[i][1]; if (!flags.contains(pointLT)) flags.add(pointLT); else flags.remove(pointLT); if (!flags.contains(pointLB)) flags.add(pointLB); else flags.remove(pointLB); if (!flags.contains(pointRT)) flags.add(pointRT); else flags.remove(pointRT); if (!flags.contains(pointRB)) flags.add(pointRB); else flags.remove(pointRB); } if(flags.size()==4 && flags.contains(left+" "+top) && flags.contains(left+" "+bottom) && flags.contains(right+" "+bottom) && flags.contains(right+" "+top)){ return totalArea == (right - left) * (top - bottom); } return false; }

http://www.guoting.org/leetcode/leetcode-391-perfect-rectangle/
http://www.voidcn.com/blog/corpsepiges/article/p-6194803.html
1.我们都知道,一个矩形是由四个顶点组成的,如果让许多个小矩形能够拼接成一个大矩形,那么除了大矩形四个顶点的坐标之外,其它的坐标应该都出现两次,这样才能保证完全覆盖
2.光满足第一点还不可以,比如题目中的Example 4,虽然满足条件一,但是出现了重复,所以需要满足下面的一点:大矩形的面积应该是所有小矩形的面积之和
所以,需要判断题目中给定的坐标能不能满足以上两点,满足的话,就可以构成一个矩形。
    public boolean isRectangleCover(int[][] rectangles) {
        if(rectangles==null||rectangles.length==0) return false;
        int x1=Integer.MAX_VALUE,x2=Integer.MIN_VALUE,y1=Integer.MAX_VALUE,y2=Integer.MIN_VALUE;
        Set<String> set=new HashSet<>();
        int area=0;
        for(int[] rect:rectangles){
            x1=Math.min(x1,rect[0]);
            y1=Math.min(y1,rect[1]);
            x2=Math.max(x2,rect[2]);
            y2=Math.max(y2,rect[3]);

            area+=(rect[2]-rect[0])*(rect[3]-rect[1]);

            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.contains(s1))
                set.remove(s1);
            else
                set.add(s1);

            if(set.contains(s2))
                set.remove(s2);
            else
                set.add(s2);

            if(set.contains(s3))
                set.remove(s3);
            else
                set.add(s3);

            if(set.contains(s4))
                set.remove(s4);
            else
                set.add(s4);
        }
        if(!set.contains(x1+" "+y1)||!set.contains(x1+" "+y2)||!set.contains(x2+" "+y1)||!set.contains(x2+" "+y2)||set.size()!=4) return false;
        return area==(x2-x1)*(y2-y1);
    }
Best: https://discuss.leetcode.com/topic/55923/o-n-solution-by-counting-corners-with-detailed-explaination

The following code passes through not only the OJ but also various test cases others have pointed out.

Idea

0_1472399247817_perfect_rectangle.jpg
Consider how the corners of all rectangles appear in the large rectangle if there's a perfect rectangular cover.
Rule 1: The local shape of the corner has to follow one of the three following patterns
  • Corner of the large rectangle (blue): it occurs only once among all rectangles
  • T-junctions (green): it occurs twice among all rectangles
  • Cross (red): it occurs four times among all rectangles
Rule 2: A point can only be the top-left corner of at most one sub-rectangle. Similarly it can be the top-right/bottom-left/bottom-right corner of at most one sub-rectangle. Otherwise overlaps occur.

Proof of correctness

Obviously, any perfect cover satisfies the above rules. So the main question is whether there exists an input which satisfy the above rules, yet does not compose a rectangle.
First, any overlap is not allowed based on the above rules because
  • aligned overlap like [[0, 0, 1, 1], [0, 0, 2, 2]] are rejected by Rule 2.
  • unaligned overlap will generate a corner in the interior of another sub-rectangle, so it will be rejected by Rule 1.
Second, consider the shape of boundary for the combined shape. The cross pattern does not create boundary. The corner pattern generates a straight angle on the boundary, and the T-junction generates a straight border.
So the shape of the union of rectangles has to be rectangle(s).
Finally, if there are more than two non-overlapping rectangles, at least 8 corners will be found, and cannot be matched to the 4 bounding box corners (be reminded we have shown that there is no chance of overlapping).
So the cover has to be a single rectangle if all above rules are satisfied.

Algorithm

  • Step1: Based on the above idea we maintain a mapping from (x, y)->mask by scanning the sub-rectangles from beginning to end.
    • (x, y) corresponds to corners of sub-rectangles
    • mask is a 4-bit binary mask. Each bit indicates whether there have been a sub-rectangle with a top-left/top-right/bottom-left/bottom-right corner at (x, y). If we see a conflict while updating mask, it suffice to return a false during the scan.
    • In the meantime we obtain the bounding box of all rectangles (which potentially be the rectangle cover) by getting the upper/lower bound of x/y values.
  • Step 2: Once the scan is done, we can just browse through the unordered_map to check the whether the mask corresponds to a T junction / cross, or corner if it is indeed a bounding box corner.
    (note: my earlier implementation uses counts of bits in mask to justify corners, and this would not work with certain cases as @StefanPochmann points out).

Complexity

The scan in step 1 is O(n) because it loop through rectangles and inside the loop it updates bounding box and unordered_map in O(1) time.
Step2 visits 1 corner at a time with O(1) computations for at most 4n corners (actually much less because either corner overlap or early stopping occurs). So it's also O(n).

    public boolean isRectangleCover(int[][] rectangles) {
        int left = Integer.MAX_VALUE, down = Integer.MAX_VALUE;
        int right = Integer.MIN_VALUE, up = Integer.MIN_VALUE;
        
        Map<Integer, HashMap<Integer, Integer>> map = new HashMap<>();
        for (int i = 0; i < rectangles.length; i++) {
            left = Math.min(left, rectangles[i][0]);
            down = Math.min(down, rectangles[i][1]); 
            right = Math.max(right, rectangles[i][2]);
            up = Math.max(up, rectangles[i][3]);
            if (!helper(map, rectangles[i][0], rectangles[i][1], 1)) return false;
            if (!helper(map, rectangles[i][2], rectangles[i][1], 2)) return false;
            if (!helper(map, rectangles[i][2], rectangles[i][3], 4)) return false;
            if (!helper(map, rectangles[i][0], rectangles[i][3], 8)) return false;
        }
        
        for (Integer x : map.keySet()) {
            for (Integer y : map.get(x).keySet()) {
                Integer v = map.get(x).get(y);
                if ((x == left || x == right) && (y == up || y == down)) {
                    if (v != 1 && v != 2 && v != 4 && v != 8) return false;
                } else {
                    if (v != 3 && v != 6 && v != 9 && v != 12 && v != 15) return false;
                }
            }
        }
        
        return true;
    }
    private boolean helper(Map<Integer, HashMap<Integer, Integer>> map, int x, int y, int pos) {
        if (!map.containsKey(x)) map.put(x, new HashMap<>());
        if (!map.get(x).containsKey(y)) map.get(x).put(y, 0);
        if ((map.get(x).get(y) & pos) != 0) return false;
        map.get(x).put(y, map.get(x).get(y) | pos);
        
        return true;
    }
http://www.cnblogs.com/dongling/p/5831106.html
刚开始想到的一个方法是先遍历所有的矩形,找出最小的(leftMost,bottomMost)和最大的(rightMost,topMost),这是所有矩形所可能覆盖的最大的区域。然后定义一个二维数组:
int[][] area = new int[topMost-bottomMost][rightMost-leftMost],
再遍历一次所有的矩形,对矩形 rect,做如下判断:
int totalArea=0;
for(int[] rect:rectangles){
    for(int i=rect[1]-bottomMost;i<rect[3]-bottomMost;i++){
        for(int j=rect[0]-leftMost;j<rect[2]-leftMost;j++){
            totalArea++;
            if(area[i][j]>=1){//说明出现了重叠覆盖区域
                return false;
            }
            else{
                area[i][j]++;
            }
    } 
} 
当遍历完所有矩形后,首先判断
if(totalArea!=(rightMost-leftMost)*(topMost-bottomMost)){
    return false;
}
因为如果要实现完全覆盖,必须有 totalArea=(rightMost-leftMost)*(topMost-bottomMost).
满足了相等条件后,再判断是否area[][]数组中所有的数据均为1----是,则说明最大覆盖区域中的每个小单元均被覆盖了一次,满足条件,返回 true;否,则说明有的区域没有覆盖到,返回 false。
上述算法的思想是正确的,但是当输入数据量覆盖面积较大时,会出现 Memory Exceeded 的错误。考虑使用一个 bit 来表示一个单元面积,结果出现了 Time Limit Exceeded 的错误。
最终考虑使用如下算法思想:
任意一个矩形均有4个顶点,当出现Perfect Rectangle时,在最大覆盖矩形内部,所有其它矩形的任意一个顶点均会出现偶数次(因为一个矩形旁边应当有一个或三个矩形和它紧密相连,那么这个相接的顶点就出现了偶数次)。所以,可以构建一个HashSet set,以一个矩形的四个顶点的(x,y)坐标构造字符串 (x+","+y),以该字符串做键值,当set中不存在该键值时,则存入该键值;当set中存在该键值时,则删除该键值;最终set中应该只剩下四个键,这四个键即是最大覆盖矩形的四个顶点。

Java 算法实现如下(并不正确):
public class Solution {
    public boolean isRectangleCover(int[][] rectangles) {
        if(rectangles.length==0||rectangles[0].length==0){
            return false;
        }
        else{
            HashSet<String>set=new HashSet<>();
            int leftMost=Integer.MAX_VALUE;
            int bottomMost=Integer.MAX_VALUE;
            int rightMost=Integer.MIN_VALUE;
            int topMost=Integer.MIN_VALUE;
            int x1,y1,x2,y2;
            for(int[] rect:rectangles){
                x1=rect[0];
                y1=rect[1];
                x2=rect[2];
                y2=rect[3];
                //记录最靠边界的点的坐标
                if(x1<leftMost){
                    leftMost=x1;
                }
                if(y1<bottomMost){
                    bottomMost=y1;
                }
                if(x2>rightMost){
                    rightMost=x2;
                }
                if(y2>topMost){
                    topMost=y2;
                }
                //由当前考察的矩形的四个顶点的坐标构成的键值
                String key1=x1+","+y1;
                String key2=x1+","+y2;
                String key3=x2+","+y1;
                String key4=x2+","+y2;
                //删除那些出现了偶数次的键值
                if(set.contains(key1)){
                    set.remove(key1);
                }
                else{
                    set.add(key1);
                }
                
                if(set.contains(key2)){
                    set.remove(key2);
                }
                else{
                    set.add(key2);
                }
                
                if(set.contains(key3)){
                    set.remove(key3);
                }
                else{
                    set.add(key3);
                }
                
                if(set.contains(key4)){
                    set.remove(key4);
                }
                else{
                    set.add(key4);
                }
            }
            String key1=leftMost+","+bottomMost;
            String key2=leftMost+","+topMost;
            String key3=rightMost+","+bottomMost;
            String key4=rightMost+","+topMost;
            if(set.size()!=4||!set.contains(key1)||
                    !set.contains(key2)||!set.contains(key3)||
                    !set.contains(key4)){
                return false;
            }
            else{
                return true;
            }
        }
    }
}
结果出现如下错误:

如上数据所示,[0,0,3,3] 为最大覆盖矩形,两个[1,1,2,2]又都在其内部,且互相抵消掉了,所以该输入数据成功地避开了所有的检测,返回了不正确的答案 true。 改正方法是添加一个 long area 数据用以记录所有矩形的总面积,检测 area 是否和 (rightMost-leftMost)*(topMost-bottomMost)相等,若不等,则说明没有完全覆盖或者出现了重叠覆盖,返回 false;若相等,则做进一步判断。新代码如下:
Java算法实现:
public class Solution {
    public boolean isRectangleCover(int[][] rectangles) {
        if(rectangles.length==0||rectangles[0].length==0){
            return false;
        }
        else{
            HashSet<String>set=new HashSet<>();
            int leftMost=Integer.MAX_VALUE;
            int bottomMost=Integer.MAX_VALUE;
            int rightMost=Integer.MIN_VALUE;
            int topMost=Integer.MIN_VALUE;
            int x1,y1,x2,y2;
            long area=0;
            for(int[] rect:rectangles){
                x1=rect[0];
                y1=rect[1];
                x2=rect[2];
                y2=rect[3];
                area+=(x2-x1)*(y2-y1);//累积记录已遍历的矩形的面积
                //记录最靠边界的点的坐标
                if(x1<leftMost){
                    leftMost=x1;
                }
                if(y1<bottomMost){
                    bottomMost=y1;
                }
                if(x2>rightMost){
                    rightMost=x2;
                }
                if(y2>topMost){
                    topMost=y2;
                }
                if(area>(rightMost-leftMost)*(topMost-bottomMost)){
                    //目前遍历的矩形的面积已经大于了所能覆盖的面积,则一定存在了重叠
                    return false;
                }
                //由当前考察的矩形的四个顶点的坐标构成的键值
                String key1=x1+","+y1;
                String key2=x1+","+y2;
                String key3=x2+","+y1;
                String key4=x2+","+y2;
                //totalCouverCount用以记录是否出现了某个矩形完全覆盖了之前的某个矩形
                //删除那些出现了偶数次的键值
                if(set.contains(key1)){
                    set.remove(key1);
                }
                else{
                    set.add(key1);
                }
                
                if(set.contains(key2)){
                    set.remove(key2);
                }
                else{
                    set.add(key2);
                }
                
                if(set.contains(key3)){
                    set.remove(key3);
                }
                else{
                    set.add(key3);
                }
                
                if(set.contains(key4)){
                    set.remove(key4);
                }
                else{
                    set.add(key4);
                }
            }
            
            if(area!=(rightMost-leftMost)*(topMost-bottomMost)){//说明没有完全覆盖或出现了重叠覆盖
                return false;
            }
            
            String key1=leftMost+","+bottomMost;
            String key2=leftMost+","+topMost;
            String key3=rightMost+","+bottomMost;
            String key4=rightMost+","+topMost;
            if(set.size()!=4||!set.contains(key1)||
                    !set.contains(key2)||!set.contains(key3)||
                    !set.contains(key4)){
                return false;
            }
            else{
                return true;
            }
        }
    }
}
https://discuss.leetcode.com/topic/55944/o-n-log-n-sweep-line-solution
Standard sweep line solution. Basic idea: Sort by x-coordinate. Insert y-interval into TreeSet, and check if there are intersections. Delete y-interval.
this way first to sort x-coordinate in order to handle rectangle from left to right when the time is same then sort by the rect[0], why do like this?
this situation happens in like top-right in 4th and bottom-left in 5th point in the below picture. 0_1472484105868_upload-06c78900-1de6-41a0-b7da-21c4511b25f9
Because we want to handle rectangle from left to right and every handle process there is only one rectangle in the vertical range, when handle 5th rectangle 4th rect should be removed, handle 2th rect 1th rect should be removed. So we need sort by rect[0] when time is same.
After the traversal sequence is set by PriorityQueue, we use the treeSet to judge two rect is intersections or not, and we can see every handle process, the yRange should equal the high of the largest rectangle outside if it is true.
For example, so basically we have three rects: Rect 1 (1, 1, 3, 3); Rect2 (1, 3, 3, 4); and Rect3 (2, 3, 3, 4). Rect3 intersects with Rect2 obviously.
So what the tree set does is that, when the sweep line goes to the time 2 (x = 2), the tree set still contains Rect2(1, 3, 3, 4) because the right time event (time=3) has not been polled from the priority queue. which means the shaded area is kind of like a horizontal blocking space (x >= 2, 3 <= y <= 4) whenever the new rect is not on the shaded area's bottom left or top right, there is an intersection.
And the set.add() will return false when the compare func returns 0.
alt text
public class Event implements Comparable<Event> {
 int time;
 int[] rect;

 public Event(int time, int[] rect) {
  this.time = time;
  this.rect = rect;
 }
 
 public int compareTo(Event that) {
  if (this.time != that.time) return this.time - that.time;
  else return this.rect[0] - that.rect[0];
 }
}

public boolean isRectangleCover(int[][] rectangles) {
 PriorityQueue<Event> pq = new PriorityQueue<Event> ();
        // border of y-intervals
 int[] border= {Integer.MAX_VALUE, Integer.MIN_VALUE};
 for (int[] rect : rectangles) {
  Event e1 = new Event(rect[0], rect);
  Event e2 = new Event(rect[2], rect);
  pq.add(e1);
  pq.add(e2);
  if (rect[1] < border[0]) border[0] = rect[1];
  if (rect[3] > border[1]) border[1] = rect[3];
 }
 TreeSet<int[]> set = new TreeSet<int[]> (new Comparator<int[]> () {
  @Override
                // if two y-intervals intersects, return 0
  public int compare (int[] rect1, int[] rect2) {
   if (rect1[3] <= rect2[1]) return -1;
   else if (rect2[3] <= rect1[1]) return 1;
   else return 0;
  }
 });
 int yRange = 0;
 while (!pq.isEmpty()) {
  int time = pq.peek().time;
  while (!pq.isEmpty() && pq.peek().time == time) {
   Event e = pq.poll();
   int[] rect = e.rect;
   if (time == rect[2]) {
    set.remove(rect);
    yRange -= rect[3] - rect[1];
   } else {
    if (!set.add(rect)) return false;
    yRange += rect[3] - rect[1];
   }
  }
                // check intervals' range
  if (!pq.isEmpty() && yRange != border[1] - border[0]) {
                        return false;
   //if (set.isEmpty()) return false;
   //if (yRange != border[1] - border[0]) return false;
  }
 }
 return true;
}
https://segmentfault.com/a/1190000006739199
== Wrong answer, doesn't work
ERROR: [[0,0,1,1],[0,1,3,2],[1,0,2,2]] expected false but return true
    public boolean isRectangleCover(int[][] A) {
        int m = A.length;
        int minlbrow = Integer.MAX_VALUE, minlbcol = Integer.MAX_VALUE, maxrurow = 0, maxrucol = 0;
        for (int i = 0; i < m; i++) {
            minlbrow = Math.min(minlbrow, A[i][1]);
            minlbcol = Math.min(minlbcol, A[i][0]);
            maxrurow = Math.max(maxrurow, A[i][3]);
            maxrucol = Math.max(maxrucol, A[i][2]);
        }
        int[] largest = {minlbrow, minlbcol, maxrurow, maxrucol};
        int alarge = area(largest);
        int asum = 0;
        for (int i = 0; i < m; i++) {
            asum += area(A[i]);
        }
        return asum == alarge;
    }
    public int area(int[] a) {
        if (a.length != 4) return 0;
        return (a[2]-a[0]) * (a[3]-a[1]);
    }



No comments:

Post a Comment

Labels

GeeksforGeeks (976) Algorithm (811) LeetCode (652) to-do (599) Review (360) Classic Algorithm (334) Classic Interview (298) Dynamic Programming (263) Google Interview (233) LeetCode - Review (233) Tree (146) POJ (137) Difficult Algorithm (136) EPI (127) Different Solutions (119) Bit Algorithms (110) Cracking Coding Interview (110) Smart Algorithm (109) Math (91) HackerRank (85) Lintcode (83) Binary Search (73) Graph Algorithm (73) Greedy Algorithm (61) Interview Corner (61) Binary Tree (58) List (58) DFS (56) Algorithm Interview (53) Advanced Data Structure (52) Codility (52) ComProGuide (52) LeetCode - Extended (47) USACO (46) Geometry Algorithm (45) BFS (43) Data Structure (42) Mathematical Algorithm (42) ACM-ICPC (41) Jobdu (39) Interval (38) Recursive Algorithm (38) Stack (38) String Algorithm (38) Binary Search Tree (37) Knapsack (37) Codeforces (36) Introduction to Algorithms (36) Matrix (36) Must Known (36) Beauty of Programming (35) Sort (35) Space Optimization (34) Array (33) Trie (33) prismoskills (33) Segment Tree (32) Union-Find (32) Backtracking (31) HDU (31) Google Code Jam (30) Permutation (30) Puzzles (30) Array O(N) (29) Data Structure Design (29) Company-Zenefits (28) Microsoft 100 - July (28) to-do-must (28) Random (27) Sliding Window (27) GeeksQuiz (25) Logic Thinking (25) hihocoder (25) High Frequency (23) Palindrome (23) Algorithm Game (22) Company - LinkedIn (22) Graph (22) Hash (22) Queue (22) DFS + Review (21) TopCoder (21) Binary Indexed Trees (20) Brain Teaser (20) CareerCup (20) Company - Twitter (20) Pre-Sort (20) Company-Facebook (19) UVA (19) Probabilities (18) Follow Up (17) Codercareer (16) Company-Uber (16) Game Theory (16) Heap (16) Shortest Path (16) String Search (16) Topological Sort (16) Tree Traversal (16) itint5 (16) Iterator (15) Merge Sort (15) O(N) (15) Bisection Method (14) Difficult (14) Number (14) Number Theory (14) Post-Order Traverse (14) Priority Quieue (14) Amazon Interview (13) BST (13) Basic Algorithm (13) Codechef (13) Majority (13) mitbbs (13) Combination (12) Computational Geometry (12) KMP (12) Long Increasing Sequence(LIS) (12) Modify Tree (12) Reconstruct Tree (12) Reservoir Sampling (12) 尺取法 (12) AOJ (11) DFS+Backtracking (11) Fast Power Algorithm (11) Graph DFS (11) LCA (11) LeetCode - DFS (11) Ordered Stack (11) Princeton (11) Tree DP (11) 挑战程序设计竞赛 (11) Binary Search - Bisection (10) Company - Microsoft (10) Company-Airbnb (10) Euclidean GCD (10) Facebook Hacker Cup (10) HackerRank Easy (10) Reverse Thinking (10) Rolling Hash (10) SPOJ (10) Theory (10) Tutorialhorizon (10) X Sum (10) Coin Change (9) Divide and Conquer (9) Lintcode - Review (9) Mathblog (9) Max-Min Flow (9) Stack Overflow (9) Stock (9) Two Pointers (9) Book Notes (8) Bottom-Up (8) DP-Space Optimization (8) Graph BFS (8) LeetCode - DP (8) LeetCode Hard (8) Prefix Sum (8) Prime (8) Suffix Tree (8) System Design (8) Tech-Queries (8) Time Complexity (8) Use XOR (8) 穷竭搜索 (8) Algorithm Problem List (7) DFS+BFS (7) Facebook Interview (7) Fibonacci Numbers (7) Game Nim (7) HackerRank Difficult (7) Hackerearth (7) Interval Tree (7) Linked List (7) Longest Common Subsequence(LCS) (7) Math-Divisible (7) Miscs (7) O(1) Space (7) Probability DP (7) Radix Sort (7) Simulation (7) Xpost (7) n00tc0d3r (7) 蓝桥杯 (7) Bucket Sort (6) Catalan Number (6) Classic Data Structure Impl (6) DFS+DP (6) DP - Tree (6) How To (6) Interviewstreet (6) Kadane’s Algorithm (6) Knapsack - MultiplePack (6) Level Order Traversal (6) Manacher (6) Minimum Spanning Tree (6) One Pass (6) Programming Pearls (6) Quick Select (6) Rabin-Karp (6) Randomized Algorithms (6) Sampling (6) Schedule (6) Suffix Array (6) Threaded (6) reddit (6) AI (5) Art Of Programming-July (5) Big Data (5) Brute Force (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Crazyforcode (5) DFS+Cache (5) DP-Multiple Relation (5) DP-Print Solution (5) Dutch Flag (5) Fast Slow Pointers (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Inversion (5) Java (5) Kadane - Extended (5) Matrix Chain Multiplication (5) Microsoft Interview (5) Morris Traversal (5) Pruning (5) Quadtrees (5) Quick Partition (5) Quora (5) SPFA(Shortest Path Faster Algorithm) (5) Subarray Sum (5) Sweep Line (5) Traversal Once (5) TreeMap (5) jiuzhang (5) to-do-2 (5) 单调栈 (5) 树形DP (5) 1point3acres (4) Anagram (4) Approximate Algorithm (4) Backtracking-Include vs Exclude (4) Brute Force - Enumeration (4) Chess Game (4) Company-Amazon (4) Consistent Hash (4) Convex Hull (4) Cycle (4) DP-Include vs Exclude (4) Dijkstra (4) Distributed (4) Eulerian Cycle (4) Flood fill (4) Graph-Classic (4) HackerRank AI (4) Histogram (4) Kadane Max Sum (4) Knapsack - Mixed (4) Knapsack - Unbounded (4) Left and Right Array (4) MinMax (4) Multiple Data Structures (4) N Queens (4) Nerd Paradise (4) Parallel Algorithm (4) Practical Algorithm (4) Pre-Sum (4) Probability (4) Programcreek (4) Quick Sort (4) Spell Checker (4) Stock Maximize (4) Subsets (4) Sudoku (4) Symbol Table (4) TreeSet (4) Triangle (4) Water Jug (4) Word Ladder (4) algnotes (4) fgdsb (4) 最大化最小值 (4) A Star (3) Abbreviation (3) Algorithm - Brain Teaser (3) Algorithm Design (3) Anagrams (3) B Tree (3) Big Data Algorithm (3) Binary Search - Smart (3) Caterpillar Method (3) Coins (3) Company - Groupon (3) Company - Indeed (3) Cumulative Sum (3) DP-Fill by Length (3) DP-Two Variables (3) Dedup (3) Dequeue (3) Dropbox (3) Easy (3) Edit Distance (3) Expression (3) Finite Automata (3) Forward && Backward Scan (3) Github (3) GoLang (3) Include vs Exclude (3) Joseph (3) Jump Game (3) Knapsack-多重背包 (3) LeetCode - Bit (3) LeetCode - TODO (3) Linked List Merge Sort (3) LogN (3) Master Theorem (3) Maze (3) Min Cost Flow (3) Minesweeper (3) Missing Numbers (3) NP Hard (3) Online Algorithm (3) Pascal's Triangle (3) Pattern Match (3) Project Euler (3) Rectangle (3) Scala (3) SegmentFault (3) Stack - Smart (3) State Machine (3) Streaming Algorithm (3) Subset Sum (3) Subtree (3) Transform Tree (3) Two Pointers Window (3) Warshall Floyd (3) With Random Pointer (3) Word Search (3) bookkeeping (3) codebytes (3) Activity Selection Problem (2) Advanced Algorithm (2) AnAlgorithmADay (2) Application of Algorithm (2) Array Merge (2) BOJ (2) BT - Path Sum (2) Balanced Binary Search Tree (2) Bellman Ford (2) Binomial Coefficient (2) Bit Mask (2) Bit-Difficult (2) Bloom Filter (2) Book Coding Interview (2) Branch and Bound Method (2) Clock (2) Codesays (2) Company - Baidu (2) Complete Binary Tree (2) DFS+BFS, Flood Fill (2) DP - DFS (2) DP-3D Table (2) DP-Classical (2) DP-Output Solution (2) DP-Slide Window Gap (2) DP-i-k-j (2) DP-树形 (2) Distributed Algorithms (2) Divide and Conqure (2) Doubly Linked List (2) GoHired (2) Graham Scan (2) Graph - Bipartite (2) Graph BFS+DFS (2) Graph Coloring (2) Graph-Cut Vertices (2) Hamiltonian Cycle (2) Huffman Tree (2) In-order Traverse (2) Include or Exclude Last Element (2) Information Retrieval (2) Interview - Linkedin (2) Invariant (2) Islands (2) Knuth Shuffle (2) LeetCode - Recursive (2) Linked Interview (2) Linked List Sort (2) Longest SubArray (2) Lucene-Solr (2) MST (2) MST-Kruskal (2) Math-Remainder Queue (2) Matrix Power (2) Minimum Vertex Cover (2) Negative All Values (2) Number Each Digit (2) Numerical Method (2) Object Design (2) Order Statistic Tree (2) Palindromic (2) Parentheses (2) Parser (2) Peak (2) Programming (2) Range Minimum Query (2) Reuse Forward Backward (2) Robot (2) Rosettacode (2) Scan from right (2) Search (2) Shuffle (2) Sieve of Eratosthenes (2) SimHash (2) Simple Algorithm (2) Skyline (2) Spatial Index (2) Stream (2) Strongly Connected Components (2) Summary (2) TV (2) Tile (2) Traversal From End (2) Tree Sum (2) Tree Traversal Return Multiple Values (2) Word Break (2) Word Graph (2) Word Trie (2) Young Tableau (2) 剑指Offer (2) 数位DP (2) 1-X (1) 51Nod (1) Akka (1) Algorithm - How To (1) Algorithm - New (1) Algorithm Series (1) Algorithms Part I (1) Analysis of Algorithm (1) Array-Element Index Negative (1) Array-Rearrange (1) Auxiliary Array (1) Auxiliary Array: Inc&Dec (1) BACK (1) BK-Tree (1) BZOJ (1) Basic (1) Bayes (1) Beauty of Math (1) Big Integer (1) Big Number (1) Binary (1) Binary Tree Variant (1) Bipartite (1) Bit-Missing Number (1) BitMap (1) BitMap index (1) BitSet (1) Bug Free Code (1) BuildIt (1) C/C++ (1) CC Interview (1) Cache (1) Calculate Height at Same Recusrion (1) Cartesian tree (1) Check Tree Property (1) Chinese (1) Circular Buffer (1) Code Quality (1) Codesolutiony (1) Company - Alibaba (1) Company - Palantir (1) Company - WalmartLabs (1) Company-Apple (1) Company-Epic (1) Company-Salesforce (1) Company-Snapchat (1) Company-Yelp (1) Compression Algorithm (1) Concurrency (1) Convert BST to DLL (1) Convert DLL to BST (1) Custom Sort (1) Cyclic Replacement (1) DFS-Matrix (1) DP - Probability (1) DP Fill Diagonal First (1) DP-Difficult (1) DP-End with 0 or 1 (1) DP-Fill Diagonal First (1) DP-Graph (1) DP-Left and Right Array (1) DP-MaxMin (1) DP-Memoization (1) DP-Node All Possibilities (1) DP-Optimization (1) DP-Preserve Previous Value (1) DP-Print All Solution (1) Database (1) Detect Negative Cycle (1) Directed Graph (1) Do Two Things at Same Recusrion (1) Domino (1) Dr Dobb's (1) Duplicate (1) Equal probability (1) External Sort (1) FST (1) Failure Function (1) Fraction (1) Front End Pointers (1) Funny (1) Fuzzy String Search (1) Game (1) Generating Function (1) Generation (1) Genetic algorithm (1) GeoHash (1) Geometry - Orientation (1) Google APAC (1) Graph But No Graph (1) Graph Transpose (1) Graph Traversal (1) Graph-Coloring (1) Graph-Longest Path (1) Gray Code (1) HOJ (1) Hanoi (1) Hard Algorithm (1) How Hash (1) How to Test (1) Improve It (1) In Place (1) Inorder-Reverse Inorder Traverse Simultaneously (1) Interpolation search (1) Interview (1) Interview - Easy (1) Interview - Facebook (1) Isomorphic (1) JDK8 (1) K Dimensional Tree (1) Knapsack - Fractional (1) Knapsack - ZeroOnePack (1) Knight (1) Kosaraju’s algorithm (1) Kruskal (1) Kruskal MST (1) Kth Element (1) Least Common Ancestor (1) LeetCode - Binary Tree (1) LeetCode - Coding (1) LeetCode - Detail (1) LeetCode - Related (1) LeetCode Diffcult (1) Linked List Reverse (1) Linkedin (1) Linkedin Interview (1) Local MinMax (1) Logic Pattern (1) Longest Common Subsequence (1) Longest Common Substring (1) Longest Prefix Suffix(LPS) (1) Manhattan Distance (1) Map && Reverse Map (1) Math - Induction (1) Math-Multiply (1) Math-Sum Of Digits (1) Matrix - O(N+M) (1) Matrix BFS (1) Matrix Graph (1) Matrix Search (1) Matrix+DP (1) Matrix-Rotate (1) Max Min So Far (1) Median (1) Memory-Efficient (1) MinHash (1) MinMax Heap (1) Monotone Queue (1) Monto Carlo (1) Multi-Reverse (1) Multiple DFS (1) Multiple Tasks (1) Next Successor (1) Offline Algorithm (1) PAT (1) Parent-Only Tree (1) Partition (1) Path Finding (1) Patience Sort (1) Persistent (1) Pigeon Hole Principle (1) Power Set (1) Pratical Algorithm (1) Probabilistic Data Structure (1) Proof (1) Python (1) Queue & Stack (1) RSA (1) Ranking (1) Rddles (1) ReHash (1) Realtime (1) Recurrence Relation (1) Recursive DFS (1) Recursive to Iterative (1) Red-Black Tree (1) Region (1) Regular Expression (1) Resources (1) Reverse Inorder Traversal (1) Robin (1) Selection (1) Self Balancing BST (1) Similarity (1) Sort && Binary Search (1) String Algorithm. Symbol Table (1) String DP (1) String Distance (1) SubMatrix (1) Subsequence (1) System of Difference Constraints(差分约束系统) (1) TSP (1) Ternary Search Tree (1) Test (1) Thread (1) TimSort (1) Top-Down (1) Tournament (1) Tournament Tree (1) Transform Tree in Place (1) Tree Diameter (1) Tree Rotate (1) Trie + DFS (1) Trie and Heap (1) Trie vs Hash (1) Trie vs HashMap (1) Triplet (1) Two Data Structures (1) Two Stacks (1) USACO - Classical (1) USACO - Problems (1) UyHiP (1) Valid Tree (1) Vector (1) Wiggle Sort (1) Wikipedia (1) Yahoo Interview (1) ZOJ (1) baozitraining (1) codevs (1) cos126 (1) javabeat (1) jum (1) namic Programming (1) sqrt(N) (1) 两次dijkstra (1) 九度 (1) 二进制枚举 (1) 夹逼法 (1) 归一化 (1) 折半枚举 (1) 枚举 (1) 状态压缩DP (1) 男人八题 (1) 英雄会 (1) 逆向思维 (1)

Popular Posts