/**
* Definition for an interval.
* struct Interval {
* int start;
* int end;
* Interval() : start(0), end(0) {}
* Interval(int s, int e) : start(s), end(e) {}
* };
*/
struct Compare {
bool operator()(Interval a, Interval b){
// a comparator that defines a strickly weak ordering
// note we actually want a min heap here, but priority queue by default is a max heap. i.e. takes from right to the left
return (a.start > b.start || (a.start == b.start && a.end >= b.end) );
}
};
class Solution {
public:
int minMeetingRooms(vector<Interval>& intervals) {
if (intervals.empty()) return 0;
priority_queue<Interval, vector<Interval>, Compare> pq;
for (auto & i: intervals)
pq.push(i);
priority_queue<int, vector<int>, std::greater<int> > rooms; // a min heap to store end times
Interval curr;
while(!pq.empty()){
curr = pq.top();
pq.pop();
if (rooms.empty()) // no rooms at the moment
rooms.push(curr.end);
else {
if (curr.start >= rooms.top()){
// current meeting's starting time is after the earliest end time of all the rooms
rooms.pop();
rooms.push(curr.end);
}
else {
// current meeting's starting time is before the earliest end time of all the rooms
// we need a new room
rooms.push(curr.end);
}
}
}
// return the size of the room
return rooms.size();
}
};
Note how to declare a priority queue: use <> instead of ().
Be the first to comment
You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.