Google电面

是时间吗？  怎么会有27   33。。。

leetcode 原题

newFeeling 发表于 2016-4-3 04:45
leetcode 原题

可以给个leetcode连接吗？

参考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;

}

wyb_1221 发表于 2016-4-3 06:56
可以给个leetcode连接吗？

253. Meeting Rooms II

谢谢楼主分享！！感觉楼上说的merge interval的方法估计算最优的了？

merge Intervals,然后查找cur_start_time - last_end_time > meeting_time