/**
* 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){
// in STL::priority_queue, it is a max heap with a strickly weaker relation defined by comparator.
// i.e. they define "a goes before b" and then fetches from the right side of the array
// if we want a min heap, we need the greater element to go before the less element, then fetches from right side
return (a.start > b.start || (a.start == b.start && a.end > b.end));
}
};
class Solution {
public:
bool canAttendMeetings(vector<Interval>& intervals) {
if (intervals.empty()) return true;
// populate the priority queue
priority_queue<Interval, vector<Interval>, Compare> meetings;
for (auto & i: intervals)
meetings.push(i);
while(!meetings.empty()){
Interval curr = meetings.top();
meetings.pop();
if (meetings.empty()) return true;
else if (curr.end > meetings.top().start) // current meeting ends after next meeting starts
return false;
}
return true;
}
};
forget about the case when there is only one remaining meeting -- need to check if meetings is empty after popping out current meeting.
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.