Leetcode 253. Meeting Rooms II

 这道题的要点在于如何知道同一时间最大可能并发的会议数量。一开始的想法就是如果有会议开始那么并发数量就要加一，而一旦有会议结束就要减一；进而想到要给开始和结束时间排序。我们可以想象有一个时间轴，所有会议的开始和结束时间都是这个时间轴上的事件，那么我们按顺序遍历这个时间轴就可以知道每一个时间点的会议数量。所以方法就是把所有的开始结束点放进一个数组排序，同时标注某个时间是开始还是结束。

对此方法稍微改进，其实我们可以对开始点和结束点分别排序，然后用双指针的方式分别遍历两个数组，类似于归并排序的思路。

时间复杂度 O(nlogn) 主要用于排序

空间复杂度 O(1)

class Solution {

public:

    int minMeetingRooms(vector<vector<int>>& intervals) {

        vector<int> start,end;

        for(vector<int> pair: intervals){

            start.push_back(pair[0]);

            end.push_back(pair[1]);

        }

        sort(start.begin(), start.end());

        sort(end.begin(), end.end());

        int rooms=0;

        int maxRoom=0;

        for(int i=0,j=0; i<start.size() && j<end.size(); ){

            if(start[i]<end[j]){

                rooms++;

                maxRoom = max(maxRoom, rooms);

                i++;

            }else if(start[i]>end[j]){

                rooms--;

                j++;

            }else{

                i++;

                j++;

            }

        }

        return maxRoom;

    }

};