Google 电面

yangdaxian 发表于 2018-6-15 12:49
诶，我刚刚又想了一下，感觉好像有点不对。这个方法似乎判断的是 在现有interval内是否有一条从y=0到y=1 ...

是的，我的方法是要判断List<Interval>是不是fully overlap query的线段，例如（0，1），不一定是一个interval涵盖住了它。不知道我题目理解的对不对哈。我认为就是存在一个x值，所有y方向的interval完全盖住了（0，1）。

kexir123 发表于 2018-6-15 12:54
是的，我的方法是要判断List是不是fully overlap query的线段，例如（0，1），不一定是一个interval涵盖 ...

诶，那我感觉其实这样有点问题，比如（0，0，1/3，1/3），（1/3，1/3，2/3，2/3），（2/3，2/3，1，1），是不是就检测不出来了？不过感觉应该可以做一些修改就可以了。
祝你面试顺利啊，加油加油！

yangdaxian 发表于 2018-6-15 11:10
抱歉啊，本弱鸡还是没想出来怎么nlogn实现，求具体讲一下排序后怎么merge。。。

今天又想了一遍 merge的地方还是觉得是O(n^2) 楼主有什么进展吗？

merge的时候肯定不能只看X轴啊，因为如果和这个interval里面的方块没有重合，那X轴交叉也没意义啊，而且和任何一个interval比的时候，肯定要和里面所有的方块比，所以正常做应该是n方。30楼的思路我看了一下，理论上来讲可以，但是实在是太麻烦了，我觉得楼主被加面，可能和最优解没关系

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

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

yangdaxian 发表于 2018-6-16 12:19
根据现有的讨论来看，如果不用之前一个同学给出论文的复杂nlogn做法的话，我感觉应该是做不到nlogn的。。 ...

同意 我觉得3楼写的比较好理解 但是merge起来还是要O(n^2)

哈哈哈哈 看不了

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

很赞同。就是lc56 meeting room变形。只不过判断两个interval是否应该merge时应该call 第一问的那个function

nlogn:
1) sort rectangle :  via x, then y if x is same : nlogn
2) height[y1,y2] = sum if isConnected(prev, curr), otherwise height = curr's height. if height blocks road, break and return.  

请问：电面是直接写code，还是写 pseudo code ?