Google电面

刚刚电面大google，听起来像白人小哥，感觉要跪，做太久，各种写错。
给两个calender schedule, 要设定的meeting time interval， 返回最小的可设置schedule的起始时

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

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

时长。找出可以约的最早的时间点。如果都没有，比如例子中B的变成[0,5] [20,25] [27,33]就返回33。

参考leetcode 56 Merge Intervals

思路：

合并schedule A，B（或更多）

sort

merge intervals 返回新的interval list

线性扫描一遍，找到第一个符合meeting长度的gap

Time: O((m+n)log(m+n)) + O(m+n)

Space: O(m+n)

public int getMeetingStartTime(List<Interval> listA, List<Interval> listB, int limit) {

        if (listA == null && listB == null) return 0;

        List<Interval> list = new ArrayList<Interval>();

        if (listA != null) list.addAll(listA);

        if (listB != null) list.addAll(listB);

        if (list.size() == 0) return 0;

        Collections.sort(list, new Comparator<Interval>() {

                @Override

                public int compare(Interval i1, Interval i2) {

                        if (i1.start == i2.start) return i1.end-i2.end;

                        return i1.start-i2.start;

                }

        });

        Interval t = list.get(0);

        List<Interval> res = new ArrayList<Interval>();

        for (int i = 1; i < list.size(); i++) {

                Interval c = list.get(i);

                if (c.start <= t.end) {

                        t = new Interval(t.start, c.end);

                } else {

                        res.add(t);

                        t = c;

                }

        }

        res.add(t);

        for (int i = 1; i < res.size(); i++) {

                if (res.get(i).start-res.get(i-1).end >= limit) {

                        return res.get(i-1).end;

                }

        }

        return res.get(res.size()-1).end;

}

1. import java.util.*;
   
2. import java.io.*;
   
3. 
   
4. public class CalenderScheduler {
   
5.     //find the first time slot that can schedule the work
   
6.     public int find (int[][] schedule1, int[][] schedule2, int required) {
   
7.         List<int[]> pos = new ArrayList<int[]>();
   
8.         int lastStart = 0;
   
9.         for (int[] job : schedule1) {
   
10.             pos.add(new int[]{job[0], 1});
    
11.             pos.add(new int[]{job[1], -1});
    
12.         }
    
13.         for (int[] job : schedule2) {
    
14.             pos.add(new int[]{job[0], 1});
    
15.             pos.add(new int[]{job[1], -1});
    
16.         }
    
17.         Collections.sort(pos, (a, b) -> {
    
18.             return a[0] - b[0];
    
19.         });
    
20.         //System.out.println(pos.size() + "size #");
    
21.         int count = 0;
    
22.         int result = 0;
    
23.         for (int i = 0; i <= pos.size(); i++) {
    
24.             if (i == pos.size()) { // can only allocate after all is done;
    
25.                 result = lastStart;
    
26.                 break;
    
27.             }
    
28.             int[] now = pos.get(i);
    
29.             if (count == 0) {  // no meeting ongoing
    
30.                 if (now[0] - lastStart >= required) { // does the time slot > time required?
    
31.                     result = lastStart;
    
32.                     break;
    
33.                 }
    
34.             }
    
35.             if (now[1] == 1)
    
36.                 count++;
    
37.             if (now[1] == -1) {  
    
38.                 count--;
    
39.                 if (count == 0)
    
40.                     lastStart = now[0]; // update the possible start time;
    
41.             }
    
42.         }
    
43.         System.out.println(result);
    
44.         return result;
    
45. 
    
46.     }
    
47. 
    
48.         public static void main(String[] args) {
    
49.                 CalenderScheduler test = new CalenderScheduler();
    
50.                 int[][] a = {{0,10}, {10, 15}, {13, 20}};
    
51.         int[][] b = {{0,5}, {27, 33}};
    
52.         int[][] c = {{0,5}, {20, 25}, {27, 33}};
    
53.         test.find(a, b, 5);
    
54.         test.find(a, c, 5);
    
55.         }
    
56. }

复制代码

补充内容 (2016-4-2 09:55):
和meeting room 2类似，通过两个测试；
lastStart 记录上一次开始可以约的时间，如果到下一次发生的时间 > required申请时间， 则可以
否则约最后一个结束时间；

LZ 题不是太懂 能把example 再说说吗?

新人回复

楼主这题你当时怎么做的啊，求分享 ！！

楼主你的补充说明里面
比如例子中B的变成[0,5] [20,25] [27,33]就返回33。

不是应该返回5吗？ 如果只约5分钟的话

newbiee 发表于 2016-4-2 05:20
楼主你的补充说明里面
比如例子中B的变成[0,5] [20,25] [27,33]就返回33。

A不可以呀，要找两个共同的free time slot

有个条件忘记了，每个schedule都是按照开始时间sort过的。
第一个想法是先找到A的可约的所有time slot, 存起来。再跟B的逐一进行比较，然后小哥问我有没有更好的，我说可以两个同时search，search的同时记录当前可以定schedule的时间。贴个code的图，电面的时候写的很混乱，这个是整理过的，估计还是会有问题，欢迎批评指正。


补充内容 (2016-4-2 06:46):
typo，最后一行参数是i，大家领会精神。。

如果A，B两个List不是很长的话，是不是可以先把短的list merge到长的list，然后从这个list里找第一个可选的interval?

newbiee 发表于 2016-4-2 05:20
楼主你的补充说明里面
比如例子中B的变成[0,5] [20,25] [27,33]就返回33。

还有sche A