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.
好慢啊
