Facebook 实习两轮店面

用greedy来做可以到O(nlogn)复杂度。

1. def find_min_intervals(intervals, target):
   
2.     intervals.sort()
   
3.     res = 0
   
4.     cur_target = target[0]
   
5.     i = 0
   
6.     max_step = 0
   
7.     while i < len(intervals) and cur_target < target[1]:
   
8.         while i < len(intervals) and intervals[i][0] <= cur_target:
   
9.             max_step = max(max_step, intervals[i][1])
   
10.             i += 1
    
11.         cur_target = max_step
    
12.         res += 1
    
13.     return res if cur_target >= target[1] else 0

复制代码

cntototo 发表于 2017-2-1 06:25
感觉第二轮的题更像是greedy。先把所有intervals按start排序，然后遍历。首先我们要从那些start小于等于tar ...

可以简化一点，不用全部排序，之排序那些和target有交集的interver。然后greedy

玉米种植专业户 发表于 2017-2-22 03:06
楼主请问 第一面是 45 分钟吗？ 45 分钟 3题代码都要写出来？

对的，我写了3题的代码，只不过第3题最后没时间，面试官没有review完

感谢分享。不过45分钟三题，私以为并不太好。。。除去寒暄和问问题和出题的时间，每题面试者自己的时间其实就10分钟。首先交流的时间不够，其次只能说明你做过这题或类似的题，对面试人判断你的思考过程和编程基本功说明不了太多问题。

请问楼主第一题改成什么了~~~感谢~~

感谢楼主分享 叙述得很详细！

加油加油！