Tuesday, December 29, 2015

252. Meeting Rooms -------E

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.

A :
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.
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