facebook 二面题目求解题思路

这题就是LC上面的meeting rooms换了马甲。meeting rooms求最少需要多少个room，也就是某个时刻有几个并行的会议，这个题目求时刻有最大的并行interval数量，差不多，按照start time排一遍，再用一个heap放结束时间就可以了。贴个python版本的：

1. 
   
2. import heapq
   
3. def integraltimestamps2(intervals):
   
4.     intvs = sorted(intervals, key = lambda x : x[0])
   
5.     edges = sorted([intv[0] for intv in intervals]+[intv[1] for intv in intervals])
   
6.     results = []
   
7.     moccurs = 0
   
8.     ongoing = []
   
9.     intvid = 0
   
10.     for e in edges:
    
11.         if results and len(ongoing) == moccurs:
    
12.             results += range(results[-1]+1,e)
    
13.         while ongoing and e >= ongoing[0]:
    
14.             heapq.heappop(ongoing)
    
15.         while intvid < len(intvs) and e >= intvs[intvid][0]:
    
16.             heapq.heappush(ongoing, intvs[intvid][1])
    
17.             intvid += 1
    
18.         if len(ongoing) > moccurs:
    
19.             moccurs = len(ongoing)
    
20.             results = [e]
    
21.         elif len(ongoing) == moccurs:
    
22.             results.append(e)
    
23.     return results

复制代码

您好！
本帖隐藏的内容需要积分高于 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

Chi2829 发表于 2016-3-12 13:52
👍这个代码很简洁啊！没做过meeting room，但是这么看和skyline也很像！results可能还要去个重。 ...

研究出来了指导一下。

分段数组!!!

Chi2829 发表于 2016-3-12 13:52
👍这个代码很简洁啊！没做过meeting room，但是这么看和skyline也很像！results可能还要去个重。 ...

写了个heap的python版本。求指导。

1. import heapq
   
2. 
   
3. def frequent_timestamp2(intervals):
   
4.     intvs = sorted(intervals, key=lambda x: x[0])  # sort by starting time
   
5.     endtimes = []  # a heap to keep end times
   
6.     results = []
   
7.     maxcnt, currcnt = 1, 0  # maximum overlap count and current overlap count
   
8.     for i in range(len(intvs)):
   
9.         newstart, newend = intvs[i]  # start and end time of a new interval
   
10.         while endtimes and endtimes[0] <= newstart:
    
11.             # while start time of curr interval >= smallest end time of an visited interval, pop the old endtime from heap and check count
    
12.             oldend = heapq.heappop(endtimes)
    
13.             if currcnt > maxcnt:
    
14.                 results = range(intvs[i-1][0], oldend)
    
15.                 maxcnt = currcnt
    
16.             elif currcnt == maxcnt:
    
17.                 results += range(intvs[i-1][0], oldend)
    
18.             currcnt -= 1
    
19.         heapq.heappush(endtimes, newend)  # push endtime of curr interval to heap
    
20.         currcnt += 1
    
21.     if currcnt > maxcnt:
    
22.         results = range(intvs[-1][0], endtimes[0])
    
23.     elif currcnt == maxcnt:
    
24.         results += range(intvs[-1][0], endtimes[0])
    
25.     return results

复制代码

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

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

Chi2829 发表于 2016-3-13 00:00
他说的挺清楚的啊，我的写法和他细节有些小区别。

先对所有interval按照start time排序，得到排序后数 ...

亲，求给一个java或者c++的版本。

primbo 发表于 2016-3-13 00:03
亲，求给一个java或者c++的版本。

亲，你这不是难为我吗...转专业现在只会写写python。你当伪码看啊！