# 253 - Meeting Rooms II

## 解法一 - Merge Interval（Failed）

``````class Solution {
public:
int minMeetingRooms(vector<vector<int>>& intervals) {
// Sort the intervals
sort(intervals.begin(), intervals.end(),
[](vector<int>& a, vector<int>& b) {
return a[0] < b[0];
});

// Start checking
int minRoom = 0;

vector< vector<int> > cur;
for(auto& interval: intervals) {
if(cur.empty()) {
cur.push_back(interval);
}
else{
while(!cur.empty() and cur.back()[1] <= interval[0]) {
cur.pop_back();
}
cur.push_back(interval);
}

minRoom = max(minRoom, (int)cur.size());
}

return minRoom;
}
};
``````

``````[[9,10],[4,9],[4,17]]
``````

sort 完畢會是：

``````[[4,9],[4,17],[9,10]]
``````

## 解法二 - Min Heap 記錄最早結束的 meeting

``````class Solution {
public:
int minMeetingRooms(vector<vector<int>>& intervals) {
if(intervals.empty()) {
return 0;
}

// Sort the intervals
sort(intervals.begin(), intervals.end(),
[](const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
});

// Start checking
priority_queue<int, vector<int>, greater<int>> cur;
cur.push(intervals[0][1]);
int minRoom = 1;

for(int i = 1; i < intervals.size(); ++i) {
while(!cur.empty() and cur.top() <= intervals[i][0]) {
cur.pop();
}

cur.push(intervals[i][1]);

minRoom = max(minRoom, (int)cur.size());
}

return minRoom;
}
};
``````