1月AmazonOA

lancelot981 发表于 2016-1-29 08:19
可能我第三题说得不清楚。比如有两个operation(1,3,100), (2,4,200)，你可以将这两个op的begin和end排序， ...

所以就是先把begin和end排序，然后计算每个区间一共要加多少，最后每个区间扫描？

GUIXIANG 发表于 2016-2-7 03:38
所以就是先把begin和end排序，然后计算每个区间一共要加多少，最后每个区间扫描？

扫一遍就好，遇到begin就加，遇到end就减，一直maintain max

lancelot981 发表于 2016-1-29 08:19
可能我第三题说得不清楚。比如有两个operation(1,3,100), (2,4,200)，你可以将这两个op的begin和end排序， ...

那请问LZ，遇到这个区间的数，怎么判断是begin index 还是 end index 和 它相应的操作值呢？

lancelot981 发表于 2016-2-7 04:37
扫一遍就好，遇到begin就加，遇到end就减，一直maintain max

额。。。还是没有懂，为什么遇到begin就加，遇到end就减呢？
如果n=6, operation有两个，分别是[1,3,100]和[2,4,100],要返回的最大值应该是200.
如果按照排完序遇到begin就加，遇到end就减，就是这样？
1                 2                  3                   4
100(max)
                200(max)
                                     100
                                                           0     
最终返回当前的最大值200.

还有楼下兄弟问的，最后扫的时候，是要用排好序的begin/end里每一个值跟每个operation里的第0个元素和第1个元素比较吗？

GUIXIANG 发表于 2016-2-7 07:43
额。。。还是没有懂，为什么遇到begin就加，遇到end就减呢？
如果n=6, operation有两个，分别是[1,3,100 ...

https://www.youtube.com/watch?v=dePDHVovJlE 这个解释sweep line很清楚

lunatic 发表于 2016-2-7 09:10
https://www.youtube.com/watch?v=dePDHVovJlE 这个解释sweep line很清楚

谢谢，这就去看

请问楼主Onsite了吗，能简单介绍一下流程吗，辛苦啦！！！

jameshuang1981 发表于 2016-2-13 02:08
请问楼主Onsite了吗，能简单介绍一下流程吗，辛苦啦！！！

还没，下星期

lancelot981 发表于 2016-2-14 00:28
还没，下星期

收到，祝楼主顺利拿大offer

楼主好牛 senior的 住楼主早日拿满意的大offer