Meeting Rooms | tech::interview

Meeting Rooms | tech::interview
Given a array of pairs where each pair contains the start and end time of a meeting (as in int),
Determine if a single person can attend all the meetings
For example:
Input array { pair(1,4), pair(4, 5), pair(3,4), pair(2,3) }
Output: false
Follow up:
determine the minimum number of meeting rooms needed to hold all the meetings.
Input array { pair(1, 4), pair(2,3), pair(3,4), pair(4,5) }
Output: 2
Follow up题也可以换一种形式：
Giving lots of intervals [ai, bi], find a point intersect with the most number of intervals
和Insert/Merge Intervals也属于一类题。
第二个问可以用贪心做，把起点和终点放在一个数组里，然后排序。然后扫描这个排序好的时间点数组，是起点则当前房间+1，是重点则-1，其中扫描过程中的最大值就是最小房间数。
值得注意的是，我们需要用一种方式来区分起点和终点。下面给的方法是把终点都用负数存，排序的比较函数直接比较他们的绝对值，然后通过正负号来判断这个时间点是起点还是终点

bool attend_all(vector<pair<int,int>> meetings) {

    sort(meetings.begin(), meetings.end(), [&](pair<int,int> p0, pair<int,int> p1){

        return p0.first < p1.first;

    });

    for(size_t i = 1; i <meetings.size(); ++i) {

        if(meetings[i].first < meetings[i-1].second) return false;

    }

    return true;

}

int min_rooms(vector<Interval>& meetings) {

    vector<int> times;

    for(auto m : meetings) {

        times.push_back(m.begin);

        times.push_back(-m.end);

    }   

    sort(times.begin(), times.end(), [](int a, int b){

        return abs(a) == abs(b) ? a < b : abs(a) < abs(b);

    });   

    int ret = 0, cur = 0;

    for(auto t : times) {

        if(t >= 0) ret = max(ret, ++cur);

        else --cur;

    }

    return ret;

}

Read full article from Meeting Rooms | tech::interview