问一道airbnb面经: rectangle intersection

                                                                                                                                                问一道A家面经题：
[size=12.000000pt]             You have a plain with lots of rectangles

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

ong>
还有就是intersect with what? 如果 A 和 B intersect，B 和 C intersect，然后 A 和 C 不 intersect，那我要return 2 还是 3？

还有就是intersect with what? 如果 A 和 B intersect，B 和 C intersect，然后 A 和 C 不 intersect，那我要return 2 还是 3？

我有个初步的想法：
假设矩形的边都是水平或垂直的，每个矩形通过左上点 以及长宽来表示
首先把左上点按y坐标排序，如果y坐标相同就按x坐标排，你可以得到一个array
考虑array中第j个元素（j > 1)，根据左上点的坐标(x0,y0)以及宽高，可以得到左下点的坐标(x0,y1)
由于array已经按照y排序了，你可以查找到(x0,y1)在array中的位置，设为i。所以j之前能与j相交的矩形只能是(i,j)之间且最右端的横坐标大于x0的矩形。但是想到这想不下去了，我不知道有哪个数据结构可以在O(1)做到给定范围[i,j]，在数组中找到[i,j]中大于值val的元素个数。如果有的话，就可以总时间复杂度O(nlogn)

Hellcat 发表于 2017-9-17 00:10
我有个初步的想法：
假设矩形的边都是水平或垂直的，每个矩形通过左上点 以及长宽来表示
首先把左上点按y ...

这里不光要最右端的横坐标大于x0吧, 最左端的横坐标还要小于x1才行, 每个都查验又需要更多的时间复杂度
就你考虑的那种情况来说, 如果是array, 用值作二分查找即可, 然后用index相减可求出大于val的个数, 时间复杂度为O(nlogn), 没有超过之前排序的时间复杂度

我猜是不是只要相交就+1，然后我感觉用unionfind挺好做的

请问这个是电面的题么？

strisunshine 发表于 2017-9-17 10:07
这里不光要最右端的横坐标大于x0吧, 最左端的横坐标还要小于x1才行, 每个都查验又需要更多的时间复杂度
...

O(nlogn) 不能保证吧， 比如按照x坐标排序，对于i元素，二分查找到i之后所有x0坐标 小于 i.x1的矩形，这时候只能确保在x轴方向这些矩形重合了，还要一一检查所有y方向是否重合，最后还是线性复杂组，worst case O(n^2), 比如有n个矩阵，左上角右下角坐标分别是(k,k)， (2n-k, 2n-k) k = 1,2,.... n-1

dnlby96 发表于 2017-9-16 20:51
还有就是intersect with what? 如果 A 和 B intersect，B 和 C intersect，然后 A 和 C 不 intersect，那我 ...

想问下楼主这道题最后搞清楚了吗？ 这个情况下到底应该return 多少？

houpy 发表于 2017-12-27 14:58
想问下楼主这道题最后搞清楚了吗？ 这个情况下到底应该return 多少？

同问。。。。。

同问楼主，这个题到底应该是return多少啊