Short Java, 21 lines, nlogn solution, pretty straight forward.


  • 0
    I

    This is like a Tetris game, rotated 90 degree clockwise.

    Express a rectangle as {a,b,c,d}, sort the input array by (a, b).
    Set curA as min(a), curB as min(b), curD as max(d)

    Process sorted rect[i] if its ai equals to current curA and bi equals to curB,
    add rect[i] to a min heap, sorted by (c, b), update curB to di, until di equals curD.
    Retrieve elements from heap if they all have the same c and their b/d are consecutive,
    set curA as c, curB as the 1st b, curD as last d.

    Repeat above procedure, until all processed,
    check if curB and curD are the same as the original min(b) and max(d).

    int minA = Integer.MAX_VALUE, minB = minA, maxD = Integer.MIN_VALUE;
    for (int[] rect : rectangles) {
        minA = Math.min(minA, rect[0]);
        minB = Math.min(minB, rect[1]);
        maxD = Math.max(maxD, rect[3]);
    }
    int curA = minA, curB = minB, curD = maxD;
    Arrays.sort(rectangles, (x, y) -> x[0] != y[0] ? x[0] - y[0] : x[1] - y[1]);
    Queue<int[]> heap = new PriorityQueue<>((x, y) -> x[2] != y[2] ? x[2] - y[2] : x[1] - y[1]);
    for (int i = 0; i < rectangles.length;) {
        while (i < rectangles.length && rectangles[i][0] == curA && rectangles[i][1] == curB) {
            curB = rectangles[i][3];
            heap.offer(rectangles[i++]);
        }
        if (curB != curD) return false;
        curA = heap.peek()[2];
        curB = heap.peek()[1];
        curD = heap.poll()[3];
        while (!heap.isEmpty() && heap.peek()[2] == curA && heap.peek()[1] == curD) curD = heap.poll()[3];
    }
    return curB == minB && curD == maxD;
    

  • 1
    I

    @iambright The idea is to build this perfect rectangle from left to right, like a rotated Tetris.
    Since the input array is sorted by (a,b), so at any moment, the next rectangle must fit in the most left bottom dent currently built (maintained by a min heap), otherwise return false. It can be proved by contradiction.


Log in to reply
 

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