难度: Medium
原题连接
内容描述
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
Example 2:
Input: [[7,10],[2,4]]
Output: 1
思路 1 - 时间复杂度: O(N)- 空间复杂度: O(N)******
想象一下，现实生活中，先开始的会议还没结束前我们就又要开始一个会议的话，此时我们需要一个新的会议室
如果前面一堆先开始的会议都先于我们的新会议开始之前结束了，我们不需要新会议室
换句话说，如果前面一堆新开始的会议中结束最早的那个会议如果在新开始的会议之前结束了的话，我们不需要会议室
所以我们的思路是，先按照会议开始的时间排序，然后维护一个会议结束时间的最小堆，堆顶就是前面结束最早的那个会议的结束时间
那么对于一个新的会议出现时：
- 如果堆顶元素比新会议的开始时间更小的话，我们不需要新会议室。同时因为后面出现的新会议的开始时间更大了， 所以目前最先结束的会议永远不可能比后面新出现的会议的开始时间更大，因此我们可以pop目前最先结束的会议，即pop堆顶元素，并且将新会议的结束时间放进堆中
- 如果堆顶元素比新会议的开始时间更大的话，我们知道我们需要一个新的会议室，此时直接将新会议的结束时间放进堆中
最终堆的size就是我们需要的会议室数量
from heapq import heappush, heappop
class Solution(object):
def minMeetingRooms(self, intervals):
"""
:type intervals: List[Interval]
:rtype: int
"""
if not intervals:
return 0
intervals.sort(key = lambda x:x.start)
end = []
for it in intervals:
# if the first finished meeting m1 ends before the next meeting
# we can directly pop m1, because there is no need to add a new room
if end and end[0] <= it.start:
heappop(end)
heappush(end, it.end)
return len(end)