FB 11/04电面一轮

oio14644 发表于 2015-11-7 10:15
public static int max(Interval[] intervals) {
                // O(n*k) time space o(max-min)
                HashMap map = ne ...

The Space Complexity is too high?

stonezms 发表于 2015-11-7 06:55
难度略高啊。。。楼主strstr那题有要求用KMP么？

没有要求。

小A要当码农 发表于 2015-11-7 13:04
The Space Complexity is too high?

怎么优化？

oio14644 发表于 2015-11-8 18:49
怎么优化？

http://www.1point3acres.com/bbs/ ... adio%26sortid%3D192
和这道题楼下的解答一样

小A要当码农 发表于 2015-11-9 00:25
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=109379&extra=page%3D1%26filter%3Dsort ...

能具体一点吗？ 指的到底是哪个？ 谢谢

oio14644 发表于 2015-11-9 07:51
能具体一点吗？ 指的到底是哪个？ 谢谢

Sorry. 15楼

lz strstr这道题要求runtime是多少的算法？

oio14644 发表于 2015-11-6 15:16
什么思路比较好，我想的比较暴力一些，用个hashmap 统计 从 最小的start到最大的end中所有的可能，不知道 ...

直接用meeting room II的代码，只不过把寸end time的容器变成priority_queue, 最后返回这个queue的front就好了。

1. class Solution {
   
2. private:
   
3.     static bool compare(Interval &i1, Interval &i2){
   
4.         return i1.start < i2.start;
   
5.     }
   
6. public:
   
7.     int minMeetingRooms(vector<Interval>& intervals) {
   
8.         std::sort(intervals.begin(), intervals.end(), compare);
   
9.         std::priority_queue<int, vector<int>, std::greater<int>> endTimeOfRooms;
   
10.         for(auto it : intervals){
    
11.             if(!endTimeOfRooms.empty() && endTimeOfRooms.top() <= it.start){
    
12.                 endTimeOfRooms.pop();
    
13.                 endTimeOfRooms.push(it.end);
    
14.             }
    
15.             else
    
16.                 endTimeOfRooms.push(it.end);
    
17.         }
    
18.         return endTimeOfRooms.top();
    
19.     }
    
20. };

复制代码

补充内容 (2015-12-10 18:11):
我的基本思路就是看每个room最后的结束时间，最先结束的那个room，在结束时，其余别的room一定是被占用的 － 因为按照定义他是最先结束的。所以在这一瞬间，所有的room都在开会。
如果有问题，欢迎指正