leetcode: 253. How many meeting rooms are required at least

题目来源

• leetcode：253会议室问题

题目描述

题目解析

最小堆

分析：

• 这里一定要把所有会议全部安排完,所以一定需要遍历这些数组
• 首先,一堆会议时间是杂乱无章的,为了让其有序,我们可以将其排序,那么问题是以起始时间排序还是以终止时间排序？
• 思考,这道题我们要解决的问题是：当观察到一个会议时,需不需要另外安排会议室？
• 从这个思路来看,我们考虑的顺序是按照会议开始的时间,因此这里按照会议起始的时间来排序
• 排序后遇到的另一个问题是,当一个新会议开始的时候,我们要怎么确定这个时候是否有之前空出来的会议室
• 因此我们还要对会议的结束时间进行统计,每当一个会议开始,我们就去检查这个会议之前开始的会议的结束时间的最小值.所以我们可以维护一个最小堆用于记录结束时间.

小结：

• 先按照开始时间对这些数组进行排序
• 然后准备一个最小堆,这个最小堆维护的是当前会议之前开始的会议的结束时间.怎么维护呢？

int minMeetingRooms(std::vector<std::vector<int>>intervals){
    
    if(intervals.empty()){
    
        return 0;
    }
    
    
    int minRooms = 0;
    std::sort(intervals.begin(), intervals.end(), [](std::vector<int> &l, std::vector<int> &r){
    
        return l[0] < r[0];
    });

    std::priority_queue<int, std::vector<int>, std::greater<>> pq;
    // 第一个会议肯定是需要排序的
    pq.emplace(intervals[0][1]);
    for (int i = 1; i < intervals.size(); ++i) {
      
    	// 有一个会议室空出来了
        if(intervals[i][0] >= pq.top()){
      // 如果当前会议start >= 之前的end
            pq.pop();  // 把之前的房间空出来
        }
        pq.emplace(intervals[i][1]);
    }
    
    

    return minRooms;
}