扫描线算法，如下两种实现方式：
1. TreeMap
class Solution {
public:
int minMeetingRooms(vector<Interval>& intervals) {
map<int, int> mp;
for(auto it : intervals){
mp[it.start] += 1;
mp[it.end] -= 1;
}
int cnt = 0, res = 0;
for(auto it : mp){
cnt += it.second;
if(cnt > res) res = cnt;
}
return res;
}
};
2. 用struct来建立对应关系
class Solution {
public:
struct Point{
int val;
int isStart;
Point(int v, int i):val(v), isStart(i){}
};
int minMeetingRooms(vector<Interval>& intervals) {
if(intervals.empty()) return 0;
vector<Point> vt;
int cur = 0, res = 0;
for(auto it : intervals){
vt.push_back(Point(it.start, 1));
vt.push_back(Point(it.end, -1));
}
auto comp = [](const Point &v1, const Point &v2){
if(v1.val == v2.val){
return v1.isStart < v2.isStart;
}
return v1.val < v2.val;
};
sort(vt.begin(), vt.end(), comp);
for(int i=0; i<vt.size(); i++){
cur += vt[i].isStart;
if(cur > res) res = cur;
}
return res;
}
};
