JAVA Solution with priorityQueue, come layer by layer beat 99%, with detailed explanation


  • 0
    T

    When I saw this problem, I just thought that if we sort the rectangle with rules like:
    (1) with the start point yin increasing sequence rectangles[i][1]
    (2) if has the same y value we just sort by the x value of start point rectangles[i][0]
    then the rectangles will have these attributions:
    (1) the rectangle with the same height will be together
    then we traverse through the sorted array:
    we will find that each time the next rectangle has the same start y with the former must has the same start point by the right bottom point of the former, if not return false
    then we use a priorityQueue to store the segment which record a same base height line combined by the same start y the comparator is the height, so what we do is to from left to right, from bottom to up to splice a final rectangle, if we met the Repeat area or vacancy we will return false; we have sorted the rectangles and the rest of rectangle will not Make up for vacancies.
    Just write a test case

    [[0,0,4,1],[7,0,8,2],[6,2,8,3],[5,1,6,3],[4,0,5,1],[6,0,7,2],[4,2,5,3],[2,1,4,3],[0,1,2,2],[0,2,2,3],[4,1,5,2],[5,0,6,1]]
    

    After sorted

    [[0,0,4,1],[4,0,5,1],[5,0,6,1],[6,0,7,2],[7,0,8,2],[0,1,2,2],[2,1,4,3],[4,1,5,2],[5,1,6,3],[0,2,2,3],[4,2,5,3],[6,2,8,3]]
    

    After first combination we get the following shape
    0_1502550166917_0c873f34-7112-47ea-977e-af3dea9c3583-image.png
    The segment after combine is [0, 6, h:1], [6, 8, h:3], i=5
    After second loop
    0_1502550191730_95c9b56f-4223-4a03-b86c-1799a167ee89-image.png

    The shadow rectangle is added thei=9
    And we have 5 segment[0,2,h:2],[2,4,h:3],[4,5,h:2],[5,6,h:3], [6,8,h:2] in priorityQueue
    Then left-up,then middle up , then left up
    Then is an rectangle ,
    The main thought is add layer by layer
    Show the code :

    class Segment {
        int start;
        int end;
        int height;
        Segment(int start, int end, int height){
            this.start = start;
            this.end = end;
            this.height = height;
        }
    }
    public boolean isRectangleCover(int[][] rectangles) {
        final boolean[] tag = {false};
        Arrays.sort(rectangles, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[1] == o2[1] && o1[0] == o2[0]) {
                    tag[0] = true;
                    return -1;
                }else if (o1[1] == o2[1])return o1[0] - o2[0];
                else return o1[1] - o2[1];
            }
        });
        if (tag[0]) return false;
        PriorityQueue<Segment> que = new PriorityQueue<>(new Comparator<Segment>() {
            @Override
            public int compare(Segment o1, Segment o2) {
                if (o1.height == o2.height) {
                    return o1.start - o2.start;
                }
                return o1.height - o2.height;
            }
        });
    
        int i = solve (0, rectangles[0][0], -1, rectangles[0][1], rectangles, que);
        if (i == -1) return false;
        while (i < rectangles.length) {
            Segment seg = que.poll();
            while (!que.isEmpty()) {
                Segment tmp = que.peek();
                if (tmp.height != seg.height || tmp.start != seg.end) break;
                seg.end = que.poll().end;
            }
            if (rectangles[i][0] != seg.start || rectangles[i][1] != seg.height) return false;
            i = solve(i,seg.start,seg.end,seg.height,rectangles,que);
            if (i == -1) return false;
        }
        Segment seg = que.poll();
        while (!que.isEmpty()) {
            Segment cur = que.poll();
            if (cur.height != seg.height) {
                return false;
            }
        }
        return true;
    }
    
    private int solve(int i, int start, int limit,int base, int[][] rectangles, PriorityQueue<Segment> que) {
        int end = start;
        int h = rectangles[i][3];
        for (; i < rectangles.length; i ++) {
            if (end == limit) break;
            if (rectangles[i][1] != base) {
                if (limit == -1) {
                    if (rectangles[i][0] > end || rectangles[i][2] > end) return -1;
                }else {
                    return -1;
                }
                break;
            }
            if (rectangles[i][0] != end) return -1;
            if (h == rectangles[i][3]) {
                end = rectangles[i][2];
            }else {
                que.offer(new Segment(start, end, h));
                start = rectangles[i][0];
                end = rectangles[i][2];
                h = rectangles[i][3];
            }
        }
        if (limit != -1 && end != limit) return -1;
        que.offer(new Segment(start, end, h));
        return i;
    }
    

Log in to reply
 

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