谷歌电面

斯坦世家 发表于 2019-1-14 12:23
这个样子的话只是找到了某个任务和这个任务是否重叠，并不能找到某个时间段有几个case重叠。比如[1,3), [ ...

"schedule是一个保证有效的task list", 所以就task不会重叠，我觉得就是新task和每个旧task比较看有没有overlap就好了， O(n)？

mrno5zzz 发表于 2019-1-14 13:20
只需要o.start < n.end and n.start < o.end.
每次找到overlap之后要更新task而不是接着用原来的task

对，我也是这个思路，但感觉排序还是不能省，不然不能保证正确更新

geekzyj 发表于 2019-1-14 09:27
每一个task包含一个开始时间和一个结束时间吗？

是开始时间和时间长度，不过也就自然知道结束时间了

Beard_dragon 发表于 2019/01/14 10:54:04
感觉可以直接查找每一个task是否与这个新的task找是不是overlap. 比如task list 里的每一个task 为 o，这个新task是 n. Overlap的cases只有三种： 1） o...

这种做法好像没办法确认  n 任务要覆盖到的时间段内，初始状态已经有几个任务了。

aabaa 发表于 2019-1-15 00:53
"schedule是一个保证有效的task list", 所以就task不会重叠，我觉得就是新task和每个旧task比较看有没有o ...

比较同意你的说法

斯坦世家 发表于 2019-1-14 12:23
这个样子的话只是找到了某个任务和这个任务是否重叠，并不能找到某个时间段有几个case重叠。比如[1,3), [ ...

题目描述说 “schedule是一个保证有效的task list”，所以不需要管这个case

塔克一则 发表于 2019-1-15 02:06
对，我也是这个思路，但感觉排序还是不能省，不然不能保证正确更新

为什么排序不能省，不是只需要判断有没有overlap就好吗？