面试问题:
给定数十亿个矩形，找到与给定点 P(x,y) 重叠的最小面积的矩形
有一种简单的方法可以通过顺序处理每个矩形在 O(n) 时间内获得答案，但进一步优化它会提供大量的矩形数组。
我最好的方法是检查每个矩形，看看点是否在里面，然后计算面积并与当前最小面积进行比较。这可以一次性完成。我想不出任何其他不需要检查所有矩形的方法
最佳答案
如果您使用具有多个点查询的相同矩形集，则 R-tree数据结构允许在不检查所有矩形的情况下知道哪些矩形包含给定点
关于algorithm - 找到最小矩形内的点。 O(n) 但进一步优化，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/36590266/