Meeting Rooms II (Leetcode 253)

扫描线算法，如下两种实现方式：

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;
    }
};