Google 电面

biomedicineman 发表于 2018-6-17 01:34
很赞同。就是lc56 meeting room变形。只不过判断两个interval是否应该merge时应该call 第一问的那个funct ...

根据之前的讨论，应该是没法nlogn内完成的，不过如果你有觉得可行的具体解法欢迎写出来讨论

根据目前大家的讨论，应该是没法nlogn内完成的，不过如果有觉得可行的具体解法欢迎写出来讨论

先sort矩形,然后merge矩形,最后求最大，最小Y

先遍历一遍，把所有重叠的长方形按照四届简单合并成一个大长方形，再遍历这些大长方形，这次只用看纵坐标是否包含(0,1)了，不用排序的话复杂度应该是O(n)

StevenXie 发表于 2018-6-17 09:13
先sort矩形,然后merge矩形,最后求最大，最小Y

哥们儿我跟你想的应该一样

FML 发表于 2018-6-17 09:27
先遍历一遍，把所有重叠的长方形按照四届简单合并成一个大长方形，再遍历这些大长方形，这次只用看纵坐标是 ...

前面给过反例了～

FML 发表于 2018-6-17 09:27
先遍历一遍，把所有重叠的长方形按照四届简单合并成一个大长方形，再遍历这些大长方形，这次只用看纵坐标是 ...

前面给过反例了～

yangdaxian 发表于 2018-6-17 22:53
前面给过反例了～

之前写的时候没考虑小数，所以把判定范围扩大到了（0，2），输入格式是{左下角坐标，右上角坐标}

1. public class Main {
   
2.     public static void main(String[] args) {
   
3.         int[][] test= new int[][]{{0,0,1,1},{2,2,4,4},{1,1,5,5}};
   
4.         System.out.println(rectangleArea(test));
   
5.     }
   
6.     static class Interval{
   
7.         int lo, hi;
   
8.         List<Interval> vtc= new LinkedList<>();
   
9.         public Interval(int lo, int hi){this.lo=lo; this.hi=hi;}
   
10.     }
    
11.     public static boolean rectangleArea(int[][] rectangles) {
    
12.         Arrays.sort(rectangles, (a, b)-> a[0]==b[0]?a[1]-b[1]:a[0]-b[0]);
    
13.         List<Interval> list= new LinkedList<>();
    
14.         int s=0, e=0;
    
15.         for (int[] r: rectangles){
    
16.             if (!list.isEmpty() && r[0]<=e) e=Math.max(e, r[2]);
    
17.             else{
    
18.                 s=r[0];
    
19.                 e=r[2];
    
20.                 list.add(new Interval(s, e));
    
21.             }
    
22.             list.get(list.size()-1).vtc.add(new Interval(r[1], r[3]));
    
23.         }
    
24.         System.out.println(list.size());
    
25.         for (Interval hor: list){
    
26.             hor.vtc.sort((a,b)->(a.lo-b.lo));
    
27.             s=Integer.MIN_VALUE;
    
28.             e=0;
    
29.             for (Interval vtc: hor.vtc){
    
30.                 System.out.println(vtc.lo+" "+vtc.hi);
    
31.                 if (s!=Integer.MIN_VALUE && vtc.lo<=e) e=Math.max(e, vtc.hi);
    
32.                 else{
    
33.                     s=vtc.lo;
    
34.                     e=vtc.hi;
    
35.                 }
    
36.                 if (s>2) break;
    
37.                 if (s<=0 && e>=2) return true;
    
38.             }
    
39.         }
    
40.         return false;
    
41.     }
    
42. }

复制代码

谢谢分享！

FML 发表于 2018-6-18 02:37
之前写的时候没考虑小数，所以把判定范围扩大到了（0，2），输入格式是{左下角坐标，右上角坐标}
[mw_sh ...

前面提到的反例是{0,0,2,2},{2,2,4,4},{-1,4,0,5}这样的。（假设路是0～5），这个情况应该是没有挡住。