Google 电面

题目我之前没见到过，希望大家一起讨论一下最优解法。

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

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

请大家来讨论一下。


补充内容 (2018-6-13 09:24):
好几个同学说看不到，那我把分数降一降吧

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

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

补充内容 (2018-6-13 09:25):
[/hide=120]我当时做的是n^2的，结果是加面了，所以我想和大家讨论一下，看是否有nlogn的做法[/hide]

补充内容 (2018-6-17 07:11):
根据目前大家的讨论，应该是没法nlogn内完成的，不过如果有觉得可行的具体解法欢迎写出来讨论

补充内容 (2018-6-17 07:13):
再补充一下，上面说的没法nlogn完成是指的没有办法用常见的算法在面试时间内完成， magicsets 同学给出了一篇论文，使用了比较复杂的算法能够在nlogn时间内完成，感兴趣的同学可以下载来看看。

1. 哇，好题～
2. nlgn (排序左下角坐标y值) 可以做.
3. 和 粒扣 的Merge Intervals + rectangle overlap：
只是每次 merge时用 isOverlap()来把下一个“吃进去”。
每次“吃”时要Math.max() 打擂台 刷新最高右上角y值。
4. Merged 的 “intervals”只关心每次 “merged的大块” block了的y的最低值和最高值。
5.扫一遍merged 的“intervals” 判断有没有 某个interval 堵住了[0,1].
6.google的题果然不一样。。哪来那么多人整天自己编题啊。。

这题是可以O(nlogn)时间，不过应该并不简单。

首先注意到一个关键性质：
一堆方块可以堵住路，当且仅当存在一条连续的曲线（“栅栏”），其起点和终点分别在道路不同的两边，且对于曲线上每个点P，都存在某个方块S，使得S在P里面。

所以本质上我们是要寻找是否存在一组“连在一起”的方块，这组方块同时与x轴以及y=1相交。

“连在一起”本质上就是要求所有长方形的联通分量（connected components），所以问题的难点是怎么在O(nlogn)时间里找到所有的连通分量。找到后我们对于每个连通分量内的所有正方形看看最小最大的y值就可以了。

然后算法这篇文章（的第一部分）中有：
Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
(我上传到这里了：https://github.com/jqdocshare/docs/blob/master/plane-rect-cc.pdf)

文章是1983年的，里面还特意提了一下：

Of course, there is a naive algorithm for the problem of finding the connected components to check every pair of rectangles for their intersections, but it takes 0(n^2) time.

算法挺麻烦的，楼主可以自己看一下... 不知道这文章的168个引用中有没有提出改进的方法。


补充内容 (2018-6-14 14:12):
有些口误.. “方块”和“正方形”都是指长方形

xiaozhi1017 发表于 2018-6-16 11:22
今天又想了一遍 merge的地方还是觉得是O(n^2) 楼主有什么进展吗？

根据现有的讨论来看，如果不用之前一个同学给出论文的复杂nlogn做法的话，我感觉应该是做不到nlogn的。。。30楼同学的做法我觉得有点问题，如果想修改成符合题意的做法，还是要n^2

利口把伞溜是矩阵重叠

堵路我只能想出O(n^2)的还不好实现，碰到这种映射的就不会......

求大神指教

感谢分享！

补充内容 (2018-6-13 08:08):
将矩阵按y排序 沿着y轴从下往上扫 前一个矩阵如果和后一个矩阵overlap就save后一个矩阵 再往上找 想了很久 我只能想到O(n^2)的 哎

是不是相当于合并多个y值区间，然后判断0-1这个区间在不在合并的区间内？  时间nlogn行么？

堵路的如果没理解错 可以union find找所有连通集团 然后看连通集团y轴的跨度是否cover了0到1 这样每个矩形过一遍就可以了

devilnut 发表于 2018-6-13 08:49
堵路的如果没理解错 可以union find找所有连通集团 然后看连通集团y轴的跨度是否cover了0到1 这样每个矩形 ...

不好意思 请无视……