facebook 二面题目求解题思路

把meetroom更新的地方改一改

rs = [] # 存放时间

if currentNeed > maxNeed ：
    rs.clear()
    rs.append(currentTime)
elif currentNeed == maxNeed:
    rs.append(currentTime)

LZ觉得如何。。？

penenda 发表于 2016-3-13 01:22
把meetroom更新的地方改一改

rs = [] # 存放时间

大家一直说meetroom，能贴个题目和input output的截图么？我的没unlock。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

具体解题思路后面有附带的python和c++代码。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

有朋友问我这道题，我花了一下午时间才写出了下面的Java的Solution，用TreeSet, 经过测试了，应该bug free了，供大家参考

1.    
   
2.    // assume the input intervals are already sorted
   
3.     public static List<Integer> findTimeStamps(List<Interval> intervals) {
   
4.         if(intervals.isEmpty())
   
5.             return new ArrayList<Integer>();
   
6. 
   
7.         // overlap interval end -> overlap interval count
   
8.         Map<Integer,Integer> overlapCount = new HashMap<Integer,Integer>();
   
9.         // overlap interval end -> overlap interval start
   
10.         Map<Integer,Integer> overlapStart = new HashMap<Integer,Integer>();
    
11.         // min-heap of interval ends
    
12.         TreeSet<Integer> set = new TreeSet<Integer>();
    
13. 
    
14.         for(Interval intvl : intervals) {
    
15.             while(!set.isEmpty() && intvl.start>=set.first())
    
16.                 set.pollFirst();
    
17.             Set<Integer> smallerEnds = set.headSet(intvl.end);
    
18.                 for(int end : smallerEnds) {
    
19.                     overlapCount.put(end, overlapCount.get(end)+1);
    
20.                     overlapStart.put(end, intvl.start);
    
21.                 }
    
22.                 Integer ceilEnd = set.ceiling(intvl.end);
    
23.                 overlapCount.put(intvl.end, ceilEnd==null ? 1 : overlapCount.get(ceilEnd.intValue())+1);
    
24.                 overlapStart.put(intvl.end,intvl.start);
    
25.                 set.add(intvl.end);
    
26.         }
    
27. 
    
28.         int maxEndCount = 0;
    
29.         for(Map.Entry<Integer,Integer> entry : overlapCount.entrySet())
    
30.             maxEndCount = Math.max(entry.getValue(), maxEndCount);
    
31.                
    
32.         List<Integer> res = new ArrayList<Integer>();
    
33.         for(Map.Entry<Integer,Integer> entry : overlapCount.entrySet()) {
    
34.             if(entry.getValue()==maxEndCount) {
    
35.                 int minEnd = entry.getKey();
    
36.                 for(int i=overlapStart.get(minEnd); i<minEnd; i++)
    
37.                     res.add(i);
    
38.             }
    
39.         }
    
40.         return res;
    
41.     }
    

复制代码