j***y
发帖数: 2074 | 1 还在看Hacking a Google Interview的材料，正看到下面这段：
Question: Axis-Aligned Rectangles
Describe an algorithm that takes an unsorted array of axis‐aligned
rectangles and
returns any pair of rectangles 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. You can assume that each rectangle
object has two variables in it: the x‐y coordinates of the upper‐left
corner and the bottom‐right corner.
Good Answer: Create a sorted array of the x coordinates of the left and
right edges of the rectangles. Then, use a "scanline" to move from left to
right through the rectangles. Keep a binary search tree containing the y
coordinates of the top and bottom edges of the rectangles that overlap the
scanline. For each element of the array, check whether it is a left or right
edge. If it is a right edge, remove the corresponding top and bottom edges
from the BST. If it is a left edge, search the BST for rectangles that
overlap the current rectangle; if there is one, return the overlap. Then,
add the y coordinates of the top and bottom edges of the rectangle to the
BST. The search takes O(n log n) time, since it takes O(n log n) time to
sort the rectangles and each of the 2n iterations takes O(log n) time.
翻来覆去看了很多遍，可是还是没怎么看懂。为什么scanline是矩形右边界的时候要
remove，是左边界的时候要insert啊？还有这个“search the BST for rectangles
that overlap the current rectangle”具体是怎么样操作的啊？
大牛们能不能给详细说一下？或给点参考文献的link？
谢了先。 | b*******8
发帖数: 37364 | 2 从左到右扫描，碰到左边界，表示开始进入这个矩形，碰到右边界，表示扫描出了这个
矩形。任一时刻，同时在BST里的矩形，X轴上一定Overlap，但还要在Y轴上进行判断是
否Overlap。用BST是为了搜索，插入，删除的时间复杂度都是log级别。 | j***y
发帖数: 2074 | 3 谢谢，经你这么解释一下清楚多了。不过，代码写起来对我还是不太容易。
可以用C或者C++给个例子吗？ | b*******8
发帖数: 37364 | 4 如果要现场Coding，涉及到BST的操作可以用伪函数代替吧，如果是平衡BST那就更是如
此。其他部分并不复杂。要展开写平衡BST的构造维护，那就是一个专门的面试题目了
。 | a***r
发帖数: 93 | 5 I still have no clue how the solution works, could someone give a hint,
better with some simple code.
Thanks:) |
|
