谷歌电面

1月面的，自我介绍加项目后出的题，因为刷的题不算多，不知道是不是leetcode原题，感觉很经典，分享出来给大家参考，也拜托顺便加米啦~~

题

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

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

>
面试官最后follow up问有没有比(nlogn)更快的做法，没什么思路，要是有大神路过，还请指点一下

Beard_dragon 发表于 2019-1-14 10:54
感觉可以直接查找每一个task是否与这个新的task找是不是overlap. 比如task list 里的每一个task 为 o，这个 ...

这个样子的话只是找到了某个任务和这个任务是否重叠，并不能找到某个时间段有几个case重叠。比如[1,3), [5, 7)是原来的shedule，我要添加一个[2,6)。用你的方法能判断出确实是新task和两个task重叠，但是忽略了原来两个task是否重叠。

感觉可以直接查找每一个task是否与这个新的task找是不是overlap. 比如task list 里的每一个task 为 o，这个新task是 n. Overlap的cases只有三种： 1） o.start< n.start<o.end
2) o.start < n.end < o. End
3) n.start < o.start && n.end > o.end
这样的话时间是O(n)

每一个task包含一个开始时间和一个结束时间吗？

能想到的只是开始把不在新task区间内的task全部滤掉。

这样剩下的再用扫描线，最好情况是可能比nlogn快些的。最坏情况是nlogn.

感觉这道题应该是蠡口 期叁耳

刚看到是离口 七二舅

斯坦世家 发表于 2019/01/14 12:23:49


这个样子的话只是找到了某个任务和这个任务是否重叠，并不能找到某个时间段有几个case重叠。比如[1,3), [5, 7)是原来的shedule，我要添加一个[2,6)。用你的方法能判断出确实是新t...

我理解这道题就是查找新任务和现有任务的重叠，并不关心现有任务之间是否重叠。

Beard_dragon 发表于 2019-1-14 10:54
感觉可以直接查找每一个task是否与这个新的task找是不是overlap. 比如task list 里的每一个task 为 o，这个 ...

只需要o.start < n.end and n.start < o.end.
每次找到overlap之后要更新task而不是接着用原来的task

感觉有一丝丝像lc的meeting room题