新鲜的狗狗面试

mingzhou1987 发表于 2016-9-19 20:59
想多了，应该就是merge interval。

难道不需要merge 完以后取不是interval的区间吗？

samuelling 发表于 2016-9-20 14:09
难道不需要merge 完以后取不是interval的区间吗？

你的merge的时候其实就已经可以直接取available的time slot了，就是说如果end1 < start2, 那么end1和start2就是available的time slot. 更好的解法还是O(n)说的那个bucket sort。

use a line to scan from beginning to the end.

bobofarm 发表于 2016-9-20 09:28
use a line to scan from beginning to the end.

so-called sweep line algorithm

请问用户report的时间段是已经按照start开始时间排序好的吗？

问个naive的问题。这个机器既然可以在同一时间被多个用户使用（比如B和C），那么，available的time slot定义就有点问题了。比如，merge B和C后得到[1pm, 6pm),但是这并不代表这个时间段内不能有其他用户再用了呀。用户D也可以在[2pm, 3pm) 使用吧？还是我哪里理解的有问题？谢谢答复！

littlebearull 发表于 2016-9-22 02:02
问个naive的问题。这个机器既然可以在同一时间被多个用户使用（比如B和C），那么，available的time slot定 ...

我和你有一样的疑问啊

littlebearull 发表于 2016-9-22 02:02
问个naive的问题。这个机器既然可以在同一时间被多个用户使用（比如B和C），那么，available的time slot定 ...

我感觉他的意思仅仅是说这一天有多少时间段没有被使用过吧，可能是楼主听的没太懂- -

encorechow 发表于 2016-9-23 14:03
我感觉他的意思仅仅是说这一天有多少时间段没有被使用过吧，可能是楼主听的没太懂- -

谢谢回复！嗯嗯，这样的话，就make sense了，