leetcode 253 Meeting Rooms II
输入一个二维数组，数组的每个元素表示会议的开始时间和结束时间，问总共需要多少个会议室？
https://leetcode-cn.com/problems/meeting-rooms-ii/
解法1:区间排序法
把区间变成2个数组：start时间数组和end时间数组，并对两个数组排序。然后一个指针遍历start数组，另一个指针指向end数组。如果start时间小于end时间，房间数就加1，start时间加1，比较并记录出现过的最多房间数。start时间大于end，则所需房间数就减1，end指针加1。
解释：假设每个区间都开设了一个会议室（即加一），当遇到start>end时候，说明两个区间不想交，则减一
def min_meeting_rooms(intervals):
starts, ends = [], []
for i in intervals:
starts.append(i.start)
ends.append(i.end)
starts.sort()
ends.sort()
s, e = 0, 0
min_rooms, count = 0, 0
while s < len(starts):
if starts[s] < ends[e]:
count += 1
min_rooms = max(min_rooms, count)
s += 1
else:
count -= 1
e += 1
return min_rooms
解法2：最小堆法
最小堆minHeap，先按start排序，然后维护一个minHeap，堆顶元素是会议结束时间最早的区间，也就是end最小。每次比较top元素的end时间和当前元素的start时间，如果start>=end，说明该上一个room可以结束接下来被当前会议区间使用。最后返回堆的大小就是所需的房间数。
面试follow up: 结果要将会议名称跟对应房间号一起返回，而不仅仅是算需要的房间数目。
解释：默认每个区间都添加了房间，一个一个地开设房间，当start>=end时候，说明该上一个room可以结束接下来被当前会议区间使用，则堆中就减少了一个房间。
import heapq
def min_meeting_rooms2(intervals):
if len(intervals) == 0:
return 0
sorted_intervals = sorted(intervals, key=lambda x: x.start)
heap = []
heapq.heappush(heap, sorted_intervals[0].end)
for i in range(1, len(sorted_intervals)):
if sorted_intervals[i].start >= heap[0]:
heapq.heappop(heap)
heapq.heappush(heap, sorted_intervals[i].end)
return len(heap)