252. Meeting Rooms (E)

Given an array of meeting time intervals where intervals[i] = [starti, endi], determine if a person could attend all meetings.

Example 1:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: false
Example 2:

Input: intervals = [[7,10],[2,4]]
Output: true

Constraints:

0 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti < endi <= 106

我的答案：

class Solution {
public:
    bool canAttendMeetings(vector<vector<int>>& intervals) {
        sort(intervals.begin(), 
             intervals.end(), 
             [](const vector<int>& meeting1, const vector<int>& meeting2){
                 return meeting1[0] < meeting2[0];
             }
        );
        
        int len = intervals.size();
        for (int i=1; i<len; ++i) {
            if (intervals[i][0] < intervals[i-1][1]) 
                return false;
        }
        
        return true;
    }
};

Runtime: 28 ms, faster than 96.56% of C++ online submissions for Meeting Rooms.
Memory Usage: 12.3 MB, less than 33.25% of C++ online submissions for Meeting Rooms.

一开始想用multiset，类似skyline，但是发现对于event的multiset需要先写cmp函数，而且后面会复杂很多，不如直接对vector排序。

multiset的写法：

class Solution {
public:
    bool canAttendMeetings(vector<vector<int>>& intervals) {
        typedef pair<int, bool> Event;
        const auto cmp = [](const Event& e1, const Event& e2) {
                if (e1.first != e2.first)
                    return e1.first < e2.first;
                else {
                    return (int)e1.second < (int)e2.second;
                }
        };
        
        multiset<Event, decltype(cmp)> events{cmp};
        
        multiset<Event>::iterator it1, it2;
        for (const auto& interval:intervals) {
            it1 = events.insert({interval[0], true});
            it2 = events.insert({interval[1], false});
            

            if (it1 != events.begin() and prev(it1)->second == true) {
                return false;
            }
            if (next(it1) != events.end() and next(it1)->second == true) {
                return false;
            }
            
            if (it2 != events.begin() and prev(it2)->second == false) {
                return false;
            }
            if (next(it2) != events.end() and next(it2)->second == false) {
                return false;
            }
        }
        
        return true;
    }
};

Runtime: 40 ms, faster than 50.00% of C++ online submissions for Meeting Rooms.
Memory Usage: 13.9 MB, less than 15.84% of C++ online submissions for Meeting Rooms.

虽然速度慢了，但是熟悉了一下这个写法

中间有4个if， 主要是得满足true false true，或者false true false的顺序，multiset不能保证两个相同的元素的顺序，所以需要左右都看，否则过不了
[[6,10],[13,14],[12,14]]

更简单的写法：

class Solution {
public:
    bool canAttendMeetings(vector<vector<int>>& intervals) {
        typedef pair<int, bool> Event;
        struct cmp {
          bool operator()(const Event& e1, const Event& e2) const {
                if (e1.first != e2.first)
                    return e1.first < e2.first;
                else {
                    return (int)e1.second < (int)e2.second;
                }
          }
        };

        multiset<Event, cmp> events;
        
        multiset<Event>::iterator it1, it2;
        for (const auto& interval:intervals) {
            it1 = events.insert({interval[0], true});
            it2 = events.insert({interval[1], false});
            

            if (it1 != events.begin() and prev(it1)->second == true) {
                return false;
            }
            if (next(it1) != events.end() and next(it1)->second == true) {
                return false;
            }
            
            if (it2 != events.begin() and prev(it2)->second == false) {
                return false;
            }
            if (next(it2) != events.end() and next(it2)->second == false) {
                return false;
            }
        }
        
        return true;
    }
};