Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...]
(si < ei), determine if a person could attend all meetings.
Example 1:
Input: [[0,30],[5,10],[15,20]]
Output: false
Example 2:
Input: [[7,10],[2,4]] Output: true
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.
Use Lambda function to sort the vector
class Solution { public: bool canAttendMeetings(vector<vector<int>>& intervals) { sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){ if(a[0]==b[0]) return a[1]<b[1]; return a[0] < b[0]; }); for(int i =1; i < intervals.size(); i++){ if(intervals[i][0] < intervals[i-1][1]) return false; } return true; } };
Use min_heap to extract next earliest start time.
NOTE:
Lambda 和 comparator的 比较方式是相反的。 !~~~~~~~~~~
class Solution { public: bool canAttendMeetings(vector<vector<int>>& intervals) { if(intervals.empty()) return true; priority_queue<vector<int>, vector<vector<int>>, comparator> minHeap; for(auto & tmp : intervals){ minHeap.push(tmp); } auto pre = minHeap.top(); minHeap.pop(); while(not minHeap.empty()){ auto cur = minHeap.top(); minHeap.pop(); if(pre[1] > cur[0]) return false; pre = cur; } return true; } private: struct comparator{ bool operator()(vector<int> a, vector<int> b){ if(a[0]==b[0]){ return a[1] > b[1]; }else{ return a[0] > b[0]; } } }; };
NOTE:
Lambda 和 comparator的 比较方式是相反的。 !~~~~~~~~~~
No comments:
Post a Comment