Google 电面

yangdaxian 发表于 2018-6-15 11:13
求大神指点nlogn具体怎么做

不敢.. 还没怎么测试过..

1.     boolean canPass(int[][] rectangles)
   
2.     {
   
3.         // sort by x, sort by longer length
   
4.         Queue<int[]> q = new PriorityQueue<>((a, b) -> (a[0] == b[0] ? b[2] - b[0] : a[2] - a[0]));
   
5.         for(int[] rec : rectangles) q.offer(rec);
   
6.         int[] u = null;
   
7.         while(!q.isEmpty())
   
8.         {
   
9.             int[] p = q.poll();
   
10.             if(u == null) u = p;
    
11.             if(overlap(u, p))
    
12.             {
    
13.                 u[0] = Math.min(u[0], p[0]);
    
14.                 u[1] = Math.min(u[1], p[1]);
    
15.                 u[2] = Math.max(u[2], p[2]);
    
16.                 u[3] = Math.max(u[3], p[3]);
    
17.                 if(u[1] <= 0 && u[3] >= 1) return false;
    
18.             }
    
19.             else u = p;               
    
20.         }
    
21.         if(u[1] <= 0 && u[3] >= 1) return false; // for last merged rectangles
    
22.         return true;
    
23.     }   
    
24. 
    
25.     boolean overlap(int[] rec1, int[] rec2)
    
26.     {
    
27.         int x1 = rec1[0], x2 = rec1[2], y1 = rec1[1], y2 = rec1[3],
    
28.             x3 = rec2[0], x4 = rec2[2], y3 = rec2[1], y4 = rec2[3];
    
29.         // either x or y has no intersection
    
30.         if(x2 < x3 || x4 < x1 || y2 < y3 || y4 < y1) return false;
    
31.         return true;
    
32.     }

复制代码

肥宅快乐水 发表于 2018-6-15 11:33
不敢.. 还没怎么测试过..

[mw_shl_code=java,true]    boolean canPass(int[][] rectangles)

（如果我理解错了请指出来啊）这个做法是把长方形按照宽度排序（排序那里是不是有typo？感觉永远都是正的？），然后把重叠的不断融合起来吗？但是比如我融合了（1，1，3，3）和（2，2，4，4），那么点（1，4）本来不在长方形上，现在就在长方形上了？那之后如果有个长方形的角是（1，4），就会被错误地判断为重合了？
另外，我不是很明白为什么排序后就能保证找到所有重叠的长方形了，因为我感觉无论按照什么指标排序，总是有可能两个长方形排序后隔的很远，但其实是重叠的...

yangdaxian 发表于 2018-6-15 11:54
（如果我理解错了请指出来啊）这个做法是把长方形按照宽度排序（排序那里是不是有typo？感觉永远都是正的 ...

是的, 确实comparator 写错了, 我写的这个应该错了.

[1, 4] 现在就在长方形上了. 之前的 [1, 1, 3, 3] + [2, 2, 4, 4] 相当于变成了[1, 1, 4, 4]

现在如果有个角是[1, 4] 就会被连接起来. 假如是[1, 1, 3, 3], [2, 2, 4, 4], [1, 4, 4, 5] -> [1, 1, 4, 5]. 但是显然我写的这个不能合成这个结果..  

我觉得overlap的矩形可以被考虑成一个大的矩形.

肥宅快乐水 发表于 2018-6-15 12:13
是的, 确实comparator 写错了, 我写的这个应该错了.

[1, 4] 现在就在长方形上了. 之前的 [1, 1, 3, 3 ...

我的意思是[1, 1, 3, 3], [2, 2, 4, 4]和 [0, 4, 1, 5]，本来第三个和前两个不重叠，但如果先融合了前两个，第三个就会被视为和前两个重叠了?

yangdaxian 发表于 2018-6-15 12:19
我的意思是[1, 1, 3, 3], [2, 2, 4, 4]和 [0, 4, 1, 5]，本来第三个和前两个不重叠，但如果先融合了前两 ...

不, 不该重叠的.

应该是 sort by x, 然后用scan line. 每次过一个x update y interval.. 现在看并不容易做..

kexir123 发表于 2018-6-15 11:53
可以O(nlogn). 我的方法如下
（1）首先遍历长方形，每个长方形保存两个event (x1, y1, y2, true), (x2, y1 ...

能问一下不用线段树，在不merge的情况下如何在logn内判断是否挡住吗？

yangdaxian 发表于 2018-6-15 12:37
能问一下不用线段树，在不merge的情况下如何在logn内判断是否挡住吗？

我本来以为二分可以，不过仔细想想好像不行hhhh。按照start，end排好序后O(n)可以找到。
我认为这个就是个tradeoff,如果merge的话insert O(n), remove O(logn), query O(logn). 如果不merge insert O(logn), remove O(n), query O(n). 我觉得没必要追求的那么完美，面试不是刷题。你想想要做interval的二分代码还得自己写，太占时间了。还不如直接O(n)遍历方便：）明天google二面，之前google也面的挺多的了，感觉就是先做出来再说。

kexir123 发表于 2018-6-15 11:53
可以O(nlogn). 我的方法如下
（1）首先遍历长方形，每个长方形保存两个event (x1, y1, y2, true), (x2, y1 ...

诶，我刚刚又想了一下，感觉好像有点不对。这个方法似乎判断的是 在现有interval内是否有一条从y=0到y=1的垂直线段？但是其实这道题里即使没有这样一条线也有可能是block的，比如想象一条s形曲线？不知道我对你的做法理解的对不对

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），是不是就检测不出来了？不过感觉应该可以做一些修改就可以了。
祝你面试顺利啊，加油加油！