Java solution, how to fix it?


  • 0
    C

    It seems that my codes can not pass the missing test cases: [[0,0,3,1],[0,1,2,3],[1,0,2,1],[2,2,3,3]].

    How to fix it?

    My idea is to do sorting firstly, and then check any two neighbor rectangles overlap or not. Trying to fix the Comparator in the following codes. But also curious whether my idea can work here or not.

    /*
    [[1,1,3,3],[3,1,4,2],[3,2,4,4],[1,3,2,4],[2,3,3,4]]
    [[1,1,2,3],[1,3,2,4],[3,1,4,2],[3,2,4,4]]
    */
    public class Solution {
        private boolean in(int[] a, int[] b) {// a overlap with b ?
            //System.out.println("["+a[0]+","+a[1]+","+a[2]+","+a[3]+"]");
            //System.out.println("["+b[0]+","+b[1]+","+b[2]+","+b[3]+"]");
            if(a[0]>=b[0] && a[0]<b[2] && a[1]>=b[1] && a[1]<b[3]) return true;
            if(a[2]>b[0] && a[2]<=b[2] && a[3]>b[1] && a[3]<=b[3]) return true;
            return false;
        }
        
        public boolean isRectangleCover(int[][] rectangles) {
            int minX = Integer.MAX_VALUE, minY = Integer.MAX_VALUE;
            int maxX = Integer.MIN_VALUE, maxY = Integer.MIN_VALUE;
            int sumArea = 0;
            for(int[] r : rectangles) {
                minX = Math.min(minX, r[0]);
                minY = Math.min(minY, r[1]);
                maxX = Math.max(maxX, r[2]);
                maxY = Math.max(maxY, r[3]);
                sumArea += (r[2]-r[0]) * (r[3]-r[1]);
            }
            // verify areas
            if( sumArea != (maxX-minX)*(maxY-minY) ) return false;
            // if areas are equal, check whether overlap, if yes, return false, 
            // before check, sorting to reduce complexity to nlogn
            Arrays.sort(rectangles, new java.util.Comparator<int[]>() {
                @Override
                public int compare(int[] a, int[] b) {
                    if(a[0] < b[0]) return -1;
                    else if(a[0] > b[0]) return 1;
                    else {
                        if(a[1] < b[1]) return -1;
                        else if(a[1] > b[1]) return 1;
                        else return 0;
                    }
                }
            });
            
            for(int i = 0; i < rectangles.length-1; i++) {
                if( in(rectangles[i+1], rectangles[i]) ) return false;
            }
            
            Arrays.sort(rectangles, new java.util.Comparator<int[]>() {
                @Override
                public int compare(int[] a, int[] b) {
                    if(a[2] < b[2]) return -1;
                    else if(a[2] > b[2]) return 1;
                    else {
                        if(a[3] < b[3]) return -1;
                        else if(a[3] > b[3]) return 1;
                        else return 0;
                    }
                }
            });
            
            for(int i = 0; i < rectangles.length-1; i++) {
                if( in(rectangles[i+1], rectangles[i]) ) return false;
                
            }
            return true;
        }
    }
    

  • 0
    L
    This post is deleted!

  • 0
    C
    This post is deleted!

  • 0
    C

    @lixx2100 Yes, I know that my codes can not pass all test cases. I gave out one missing test case in my post.
    But I have no idea how to fix it.


  • 0

    Thanks, I have added the missing test cases.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.