Google 电面

yangdaxian 发表于 2018-6-18 08:29
前面提到的反例是{0,0,2,2},{2,2,4,4},{-1,4,0,5}这样的。（假设路是0～5），这个情况应该是没有挡住。

改了一下，你再看看

1. public class Main {
   
2.     public static void main(String[] args) {
   
3.         int[][] test= new int[][]{{0,0,2,2},{2,2,4,4},{-1,4,0,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 && overlap(list.get(list.size()-1).vtc, r[1], r[3])) 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>5) break;
    
37.                 if (s<=0 && e>=5) return true;
    
38.             }
    
39.         }
    
40.         return false;
    
41.     }
    
42.     public static boolean overlap(List<Interval> list, int s, int e){
    
43.         for (Interval i: list) if (Math.max(i.lo, s)<=Math.min(i.hi, e)) return true;
    
44.         return false;
    
45.     }
    
46. }

复制代码

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

同意这个方法

楼主把分数降到100可否，新农每天攒1个，要好久才到120

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

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

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

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

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

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

Anakin09 发表于 2018-6-19 01:08
哈哈哈哈哈哈lz不用一个个回复啦，认真看了前面的讨论都会有自己的判断的。

补充内容 (2018-6-19 01:09) ...

哈哈谢谢你！

yangdaxian 发表于 2018-6-19 00:05
那您再试试{0,0,10,2},{3,3,4,4},{9,1,10,6}吧，应该是挡住了，但按照这个方法是没挡住...

大概知道问题在哪儿了，不过这样就很麻烦，一小时肯定写不出来，whatever加油

kan yin cang