[数据结构与算法]LeetCode 253. Meeting Rooms II - 优先级队列（Priority Queue）系列题1

优先级队列（即最小堆或最大堆）在LeetCode中是一种经常用到的数据结构，可以大大提高算法的性能。在Python中可以使用heapq模块来实现：

本系列将挑选一些优先级队列相关的题来加强对其的掌握和应用。

Given an array of meeting time intervals?intervals?where?intervals[i] = [starti, endi], return?the minimum number of conference rooms required.

Example 1:

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

Example 2:

Input: intervals = [[7,10],[2,4]]
Output: 1

Constraints:

• 1 <=?intervals.length <= 104
• 0 <= starti?< endi?<= 106

题目给定一个区间数组intervals，每个区间intervals[i]=[starti, endi]表示一个会议的起始和结束时间。一个会议需要一个会议室，但是如果有之前的任意一个会议结束了，那么新的会议就可以使用旧的会议室而不需要申请新的会议室，否则需要申请一个新的会议室。问最多需要多少个会议室可以满足所有会议能按时召开。

会议召开的顺序是由其起始时间决定的，对于一个会议，那些起始时间比它小的会议都已经召开了，如果那些已经召开的会议中有的已经结束了，那么这个新的会议就不要申请新的会议室了，因此我们只要检查所有已经召开的会议的结束时间，只要有一个会议的结束时间是小于等于新会议的开始时间就足够了，也就是说我们只要找到最早结束的那个会议然后判断它的结束时间和新会议的开始时间就可以了。为了能快速找到最早的会议结束时间，我们可以用一个优先级队列来存放会议的结束时间，python中的heapq默认的就是最小堆，排在最前面的就是最小值，因此只要比较最小值跟当前会议的起始时间，如果其小于等于当前会议的起始间，就可以中队列中弹出，表示会议已结束，会议室可以给新会议使用，然后把新会议的结束时间再压入队列，最后队列的大小就是所需的会议室的个数。

另外，为了要保证比当前会议更早的会议都已经入列了，在判断每个会议是否需要新会议室之前需要把intervals按起始时间先排下序。

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        intervals.sort(key = lambda x:x[0])
        
        pq = []
        
        for i in intervals:
            if pq and pq[0] <= i[0]:
                heapq.heappop(pq)
                
            heapq.heappush(pq, i[1])
        
        return len(pq)