258.cpp

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
bool start_compare(Interval &a, Interval &b) { return a.start > b.start; }
bool end_compare(Interval &a, Interval &b) { return a.end > b.end; }

class Solution {
    
public:
    int minMeetingRooms(vector<Interval>& intervals) {
        priority_queue<Interval, vector<Interval>, decltype(&start_compare)> event_left(&start_compare);
        priority_queue<Interval, vector<Interval>, decltype(&end_compare)> using_room(&end_compare);
        int max_room = 0;
        for (auto interval : intervals)
        {
            event_left.push(interval);
        }
        
        while (event_left.size() > 0)
        {
            auto interval = event_left.top();
            event_left.pop();
            while (using_room.size() > 0 && using_room.top().end <= interval.start)
                using_room.pop();
            using_room.push(interval);
            int size = using_room.size();
            max_room = max(max_room, size);
        }
        return max_room;
    }
};