题目描述
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.
样例
Input: [[0, 30],[5, 10],[15, 20]]
Output: 2
算法1
Heapq 优先队列
时间复杂度
O(nln(n))
空间复杂度
O(n)
参考文献
Python3 代码
class Solution(object):
import heapq
def minMeetingRooms(self, intervals):
"""
:type intervals: List[List[int]]
:rtype: int
"""
if not intervals:
return 0
intervals.sort(key = lambda i: i[0])
heap = [intervals[0][1]]
for i in range(1,len(intervals)):
if intervals[i][0] >= heap[0]:
heapq.heappop(heap)
heapq.heappush(heap, intervals[i][1])
else:
heapq.heappush(heap, intervals[i][1])
return len(heap)
这个就是区间分组问题hh?