### Question

link, MIT handouts Person_A

Describe an algorithm that takes an unsorted array of axis-aligned rectangles and returns

any pair ofrectangles that overlaps, if there is such a pair.Axis-aligned means that all the rectangle sides are either parallel or perpendicular to the x- and y-axis.

Each rectangle object has two variables: the x-y coordinates of the upper-left corner and the bottom-right corner.

### Analysis

A lot of different solutions on the internet, example 1 and example 2, and some questions asks you to return all overlapping pairs. For now, we just return **any pair** that overlaps.

### Solution

I concluded some solution and come up with this (the idea of BST is covered in the end of this pdf):

- Sort the input by left edge.
- One by one, get one rectangle from the sorted input, and make a pair (rect.top, rect.bottom).
- Insert this pair into a
**Interval Search Tree**. - This tree is a BST, and use first value of the pair as BST key.
- Insert pair at the correct BST location. If conflicts, we’ve found 1 overlapping pair.

The code for searching a intersect, and insert a pair looks like this:

```
Node x = root;
while (x != null) {
if (x.interval.intersects(lo, hi))
return x.interval;
else if (x.left == null) x = x.right;
else if (x.left.max < lo) x = x.right;
else x = x.left;
}
return null;
```