面试遇到扫描线算法和interval tree 问题怎么办# JobHunting - 待字闺中
f*5
1 楼
最近在看和计算几何的问题，不少问题需要这2个算法，
如果遇到用到扫描线或者interval tree， 涉及到delete操作，基本不可能写完代码吧。
网上也找不到怎么使用现成的data structure库可以用，如果面试的时候想到这2个算
法，怎么处理？
求教有经验的大牛
比如Hacking google interview中 的这道题：
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.
如果遇到用到扫描线或者interval tree， 涉及到delete操作，基本不可能写完代码吧。
网上也找不到怎么使用现成的data structure库可以用，如果面试的时候想到这2个算
法，怎么处理？
求教有经验的大牛
比如Hacking google interview中 的这道题：
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.
