Google 电面

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):
有些口误.. “方块”和“正方形”都是指长方形

magicsets 发表于 2018-6-14 14:10
这题是可以O(nlogn)时间，不过应该并不简单。

首先注意到一个关键性质：

谢谢讨论！不过我大概看了一下，感觉面官不太可能指望面试者这么快想出这篇论文的算法吧。。另外由于第一道是判断两个长方形是否重合，感觉第二道应该是要直接用到第一道写的方法的。所以我感觉在面试时间内，面官应该只是期望一个n^2的算法吧。这么看来应该是写的小bug太多了...

1. 哩扣 尔尔叁
2. 哩扣五六, 但是是不太一样的merge.. 因为你得其实只merge x, 然后看他的ymin 和 ymax..

肥宅快乐水 发表于 2018-6-15 02:07
1. 哩扣 尔尔叁
2. 哩扣五六, 但是是不太一样的merge.. 因为你得其实只merge x, 然后看他的ymin 和 ymax.. ...

2的重点在于如何找到所有相连的长方形吧，倒不是merge这块。

yangdaxian 发表于 2018-6-15 02:14
2的重点在于如何找到所有相连的长方形吧，倒不是merge这块。

相连的长方形会变成一个新的大长方形, 用priority queue吧. 其实就是merge rectangle

肥宅快乐水 发表于 2018-6-15 02:37
相连的长方形会变成一个新的大长方形, 用priority queue吧. 其实就是merge rectangle

额，请问能具体说一下你的做法吗？给个伪码之类的？

aiyawocao 发表于 2018-6-14 12:24
1. 哇，好题～
2. nlgn (排序左下角坐标y值) 可以做.
3. 和 粒扣 的Merge Intervals + rectangle overlap ...

非常形象！merged的前提是overlap，这样就解决了x轴的问题。

aiyawocao 发表于 2018-6-14 12:24
1. 哇，好题～
2. nlgn (排序左下角坐标y值) 可以做.
3. 和 粒扣 的Merge Intervals + rectangle overlap ...

抱歉啊，本弱鸡还是没想出来怎么nlogn实现，求具体讲一下排序后怎么merge。。。

肥宅快乐水 发表于 2018-6-15 02:37
相连的长方形会变成一个新的大长方形, 用priority queue吧. 其实就是merge rectangle

求大神指点nlogn具体怎么做