Leetcode 253. Meeting Rooms II

Medium — sort and min priority queue

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],…] find the minimum number of conference rooms required.

For example,

[[2,15], [36,45], [8,29], [16,23], [4,9]]

meeting rooms needed: 3

class Solution {
    size_t max{0};
public:
    static bool comparator(const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    }
    
    int minMeetingRooms(vector<vector<int>>& intervals) {    
        sort(intervals.begin(), intervals.end(), comparator);
        priority_queue<int, vector<int>, greater<int>> pq;   
        for (auto const& i: intervals) {
            while(!pq.empty() && i[0] >= pq.top() ) {
                pq.pop();
            }
            pq.push(i[1]);
            if (pq.size() > max) {
                max = pq.size();
            }         
        } 
        return max;
    }
};

Priority Queue

• Priority queues are a type of container adaptors.
• its first element is always the greatest (or smallest)of the elements it contains
• less<T> is default and make the first element the greatest.
• greater<T> will make the first element the smallest