Sweep Line O(nlogn)


  • 0

    Idea is very basic that we sweep line from left to right. the next event point is a left side of rectangle with smallest x value in heap. what made code a bit long is the case that there are multiple rectangles with the same left side value (the first value of the four).

    new version

    public boolean isRectangleCover(int[][] rectangles) {
            int x1 = Integer.MAX_VALUE;
            int x2 = Integer.MAX_VALUE;
            int x3 = Integer.MIN_VALUE;
            int x4 = Integer.MIN_VALUE;
            for(int i=0; i<rectangles.length; i++) {
                x1 = Math.min(x1, rectangles[i][0]);
                x2 = Math.min(x2, rectangles[i][1]);
                x3 = Math.max(x3, rectangles[i][2]);
                x4 = Math.max(x4, rectangles[i][3]);
            }
            Arrays.sort(rectangles, (r1, r2)->{ return r1[0]!=r2[0]?r1[0]-r2[0]:r1[1]-r2[1];});
            PriorityQueue<int[]> queue = new PriorityQueue<>((r1,r2)->{return r1[2]!=r2[2]?r1[2]-r2[2]:r1[3]-r2[3];});
            queue.offer(new int[]{Integer.MIN_VALUE,x2,rectangles[0][0],x4});
            for(int i=0; i<rectangles.length; ) {
                List<int[]> oldRect = new ArrayList<>();
                List<int[]> newRect = new ArrayList<>();
                int boundary = queue.peek()[2];
                while(!queue.isEmpty()&&boundary==queue.peek()[2]) oldRect.add(queue.poll());
                while(i<rectangles.length&&boundary == rectangles[i][0]) newRect.add(rectangles[i++]);
                if(!check(oldRect, newRect)) return false;
                queue.addAll(newRect);
            }
            return true;
        }
        public boolean check(List<int[]> r1, List<int[]> r2){
           if(r1.size()==0||r2.size()==0) return false;
           List<int[]> height1 = getHeight(r1);
           List<int[]> height2 = getHeight(r2);
           if(height1.size()!=height2.size()) return false;
           for(int i=0; i<height1.size(); i++) if(height1.get(i)[0]!=height2.get(i)[0] || height1.get(i)[1]!=height2.get(i)[1]) return false;
           return true;
        }
        public List<int[]> getHeight(List<int[]> r1) {
            List<int[]> ans = new ArrayList<>();
            int[] cur = new int[]{r1.get(0)[1],r1.get(0)[3]};
            for(int i = 1; i<r1.size(); i++) {
                if(cur[1]==r1.get(i)[1]) {
                    cur[1] = r1.get(i)[3];
                } else {
                    ans.add(cur);
                    cur = new int[]{r1.get(i)[1],r1.get(i)[3]};
                }
            }
            ans.add(cur);
            return ans;
        }
    

    old version

    class Interval {
            int start;
            int end;
            public Interval(int a, int b) {
                start = a;
                end = b;
            }
        }
        public boolean isRectangleCover(int[][] rectangles) {
            if(rectangles.length==0) return false;
            int[] biggest = new int[]{rectangles[0][0],rectangles[0][1],rectangles[0][2],rectangles[0][3]};
            Map<Integer,List<Integer>> hm = new HashMap<>();
            for(int i=0;i<rectangles.length;i++) {
                biggest[0] = Math.min(biggest[0],rectangles[i][0]);
                biggest[1] = Math.min(biggest[1],rectangles[i][1]);
                biggest[2] = Math.max(biggest[2],rectangles[i][2]);
                biggest[3] = Math.max(biggest[3],rectangles[i][3]);
                if(!hm.containsKey(rectangles[i][0])) hm.put(rectangles[i][0], new ArrayList<>());
                hm.get(rectangles[i][0]).add(i);
            }
            for(List<Integer> l:hm.values()) {
                Collections.sort(l,(i1,i2)->rectangles[i1][1]-rectangles[i2][1]);
            }
    
            int line = biggest[0];
            List<Interval> bound = new ArrayList<>();
            bound.add(new Interval(biggest[1],biggest[3]));
            PriorityQueue<Integer> pq = new PriorityQueue<>((i1,i2)->{
                if(rectangles[i1][2]!=rectangles[i2][2]) return rectangles[i1][2]-rectangles[i2][2];
                else return rectangles[i1][1]-rectangles[i2][1];
            });
            int visited = 0;
            while(line<biggest[2]) {
                List<Integer> cur = hm.get(line);
                if(cur==null) return false;
                int i = 0;
                int j = 0;
                while(j<bound.size()) {
                    int low = bound.get(j).start;
                    int high = bound.get(j).end;
                    while(i<cur.size()&&low<high) {
                        int index = cur.get(i++);
                        if(rectangles[index][1]!=low) return false;
                        low = rectangles[index][3];
                        pq.offer(index);
                        visited++;
                    }
                    j++;
                    if(low>high) return false;
                }
                int next = pq.poll();
                line = rectangles[next][2];
                bound = new ArrayList<>();
                bound.add(new Interval(rectangles[next][1],rectangles[next][3]));
                int high = rectangles[next][3];
                while(!pq.isEmpty()&&rectangles[pq.peek()][2]==rectangles[next][2]) {
                    int curIndex = pq.poll();
                    if(high!=rectangles[curIndex][1]) {
                        bound.add(new Interval(rectangles[curIndex][1],rectangles[curIndex][3]));
                        high = rectangles[curIndex][3];
                    } else {
                        bound.get(bound.size()-1).end = rectangles[curIndex][3];
                        high = rectangles[curIndex][3];
                    }
                }
    
            }
            return visited==rectangles.length;
        }
    

Log in to reply
 

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