We can use the following steps to solve this problem:

- find most left, and most bottom point. if none, return false
- find most right, and most top point. if none, return false
- calculate the expected area of the rectangle defined by the above two points
- calculate the sum of all rectangles' area
- if expected area is not the same with sum of area, then return false
- if rectangles don't overlap, then return true; otherwise return false

All steps except step 6 are `O(n)`

. Step 6 can be implemented by an interval tree. First sort the rectangles's two y-axis boundary interval by x coordinate value. Now sweep from left to right. When meeting left side of the rectangle, we add the interval (parallel to y-axis) into tree; when meeting right side of the rectangle, we delete the interval from tree. Before adding, we check whether there is any interval that overlaps with the new interval. If yes, then overlap, then return false.

However, it looks like I haven't found a convenient and easily portable java interval tree implementation online.

The entire algorithm is `O(nlogn)`

because the dominant step 6 is `O(nlogn)`

.