1
class Solution {
2
  // Rectangle x0,y0,x1,y1
3
  public boolean isRectangleCover(int[][] rectangles) {
4
    // Ordered by y0 first and x0 second
5
    Arrays.sort(
6
        rectangles,
7
        (r1, r2) -> {
8
          if (r1[1] == r2[1]) return r1[0] - r2[0];
9
          return r1[1] - r2[1];
10
        });
11

12
    // Layering rectangles with pq, ordered by y1 first and x0 second
13
    PriorityQueue<int[]> pq =
14
        new PriorityQueue<>(
15
            (r1, r2) -> {
16
              if (r1[3] == r2[3]) return r1[0] - r2[0];
17
              return r1[3] - r2[3];
18
            });
19

20
    // Create first layer
21
    pq.offer(rectangles[0]);
22
    int i = 1;
23
    while (i < rectangles.length && rectangles[i][1] == rectangles[i - 1][1]) {
24
      if (rectangles[i][0] != rectangles[i - 1][2]) return false;
25
      pq.offer(rectangles[i++]);
26
    }
27

28
    while (i < rectangles.length) {
29
      int[] curr = rectangles[i++];
30
      int x = curr[0];
31
      // matching current rectangle with rectangles in the lower layer
32
      while (!pq.isEmpty() && x < curr[2]) {
33
        int[] prev = pq.poll();
34
        if (prev[3] != curr[1] || prev[0] != x) return false;
35
        if (prev[2] > curr[2]) {
36
          pq.offer(new int[] {curr[2], prev[1], prev[2], prev[3]});
37
          x = curr[2];
38
        } else {
39
          x = prev[2];
40
        }
41
      }
42
      if (x < curr[2]) return false;
43
      pq.offer(curr);
44
    }
45

46
    int[] prev = pq.poll();
47
    while (!pq.isEmpty()) {
48
      if (pq.poll()[3] != prev[3]) return false;
49
    }
50

51
    return true;
52
  }
53
}