253. Meeting Rooms II (M)

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.

Example 1:

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

Input: [[7,10],[2,4]]
Output: 1
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

我的答案：

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        typedef pair<int, bool> Event;
        vector<Event> events;
        
        for (const auto& interval:intervals) {
            events.push_back({interval[0], true});
            events.push_back({interval[1], false});
        }
        
        sort(events.begin(), events.end(), [](const Event& e1, const Event& e2){
            if (e1.first != e2.first)
                return e1.first < e2.first;
            else
                return (int)e1.second < (int)e2.second;
        }); // 0 true, 5 true, 10 false, 15 true, 20 false, 30 false
        
        int count = 0;
        int ans = 0;
        for (const auto& event:events) {
            if (event.second) {
                ++count;
                ans = max(ans, count);
            }
            else
                --count;
        }
        
        return ans;
    }
};

Runtime: 72 ms, faster than 13.18% of C++ online submissions for Meeting Rooms II.
Memory Usage: 12.8 MB, less than 44.88% of C++ online submissions for Meeting Rooms II.

好慢啊