https://leetcode.com/problems/meeting-rooms-ii/#/solutions
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.
For example,
Given [[0, 30],[5, 10],[15, 20]],
return 2.
# Definition for an interval. class Interval(object): def __init__(self, s=0, e=0): self.start = s self.end = e class Solution(object): def minMeetingRooms(self, intervals): """ :type intervals: List[Interval] :rtype: int """ intervals.sort(key = lambda x: x.start) # stores the end time of intervals heap = [] for i in intervals: if heap and i.start >= heap[0]: # means two intervals can use the same room heapq.heapreplace(heap, i.end) else: # a new room is allocated heapq.heappush(heap, i.end) return len(heap)
Note:
1 heapq.heappop() in python can pop the smallest value in the heap. Here‘s the demo.
import heapq
h = []
heapq.heappush(h, 5)
heapq.heappush(h, 2)
heapq.heappush(h, 8)
heapq.heappush(h, 4)
print(heapq.heappop(h))
print(heapq.heappop(h))
== >
2
4
2 Data structures are generally based on the ability of a computer to fetch and store data at any place in its memory.
原文：http://www.cnblogs.com/prmlab/p/7077199.html