253.Meeting Rooms II

Tags: Medium Greedy

Links: https://leetcode-cn.com/problems/meeting-rooms-ii/

---

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

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

---

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        sort(intervals.begin(), intervals.end(), [](vector<int> & a, vector<int> & b){return a[0] < b[0] || (a[0] == b[0] && a[1] < b[1]);});

        int cnt = 0;
        //使用小根堆
        priority_queue<int, vector<int>, greater<int>> pq;
        int n = intervals.size();
        for (int i = 0; i < n; ++i) {
            if (pq.empty()) { //会议室为空
                pq.push(intervals[i][1]);
                ++cnt;
            }
            else {
                int num = pq.top(); pq.pop();
                //可以安排进去
                if (num <= intervals[i][0]) {
                    pq.push(intervals[i][1]);
                }
                else {
                    ++cnt;
                    pq.push(num);
                    pq.push(intervals[i][1]);
                }
            }
        }

        return cnt;
    }
};

和POJ-3190 Stall Reservations（贪心，区间划分+路径输出）基本是一致的，在《基础算法——贪心》里已经总结。