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
// Treemap
int minMeetingRooms(vector<vector<int>>& intervals) { // time: O(nlogn); space: O(n)
map<int, int> m;
for (vector<int>& i : intervals) {
++m[i[0]];
--m[i[1]];
}
int cur = 0, res = 0;
for (auto& e : m) {
cur += e.second;
res = max(res, cur);
}
return res;
}
// Sort + Greedy
int minMeetingRooms(vector<vector<int>>& intervals) { // time: O(nlogn); space: O(n)
if (intervals.empty()) return 0;
sort(intervals.begin(), intervals.end());
priority_queue<int, vector<int>, greater<int> > pq; // min heap
pq.push(intervals[0][1]); // first end
for (int i = 1; i < intervals.size(); ++i) {
if (intervals[i][0] >= pq.top()) pq.pop();
pq.push(intervals[i][1]);
}
return pq.size();
}
// Sort
int minMeetingRooms(vector<vector<int>>& intervals) { // time: O(nlogn); space: O(n)
vector<pair<int, int> > v;
for (const vector<int>& i : intervals) {
v.push_back({i[0], 1});
v.push_back({i[1], -1});
}
sort(v.begin(), v.end());
int cur = 0, res = 0;
for (pair<int, int>& p : v) {
cur += p.second;
res = max(res, cur);
}
return res;
}