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
Why do you want to use an interval tree for that? It's overkill. You don't need to support overlapping intervals. So you can just use for example a sorted set like @wddd did.
@StefanPochmann you are right! interval tree needs to store overlapping intervals. however, we only need to store non-overlapping intervals in this question. So one treeset is enough, just let overlapping intervals "equal" to each other.