问个FB高频率Meetring Room的Follow up解答

253. Meeting Rooms II
DescriptionHintsSubmissionsDiscussSolution
Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.

Example 1:

Input: [[0, 30],[5, 10],[15, 20]]
Output: 2

以上是原题。Follow up需要输出每个meeting所在的会议室的细节。group all meetings by meeting rooms.

output： [
               [0, 30]
               [5, 10], [15, 20]
              ]

请问下怎么做？？

用一个hashmap存起来，每次加heap时也存map里。然后再用常规办法把map里的entry归归类，同一个value的key，放一起。

我不知道怎么把数组放在map里，所以用了字符串。。。。等更好的办法。  

heap解法中，入堆时，加一维属性：（start，end，room id）。

room id 是递增的。

如果当前meeting的开始时间早于队顶meeting的结束时间，那就要申请一个新的meeting room。room id加一

否则，可以复用同一个meeting room。push当前meeting入堆。同时复用room id。

collect result时用一个hashmap。key为room id，值为一组meeting。

时间复杂度和空间复杂度还是和之前一样

1. def PrintMeetingRoom(intervals):
   
2.     if not intervals:
   
3.         return []
   
4.     intervals.sort(key=lambda x: x[0])
   
5.     heap = []
   
6.     hmap = collections.defaultdict(list)
   
7.     index = 1
   
8.     for interval in intervals:
   
9.         if heap and heap[0][0] <= interval[0]:
   
10.             end, index = heapq.heappop(heap)
    
11.         hmap[index].append(interval)
    
12.         heapq.heappush(heap, (interval[1], index))
    
13.         index += 1
    
14.     return list(hmap.values())

复制代码

heap里多存一个res array的index就行了

题目刷完后，自己设想一下可能的follow-up是什么。

同时，回答一下这道题其它套路才不行？不行的话，本质原因是什么。