Tuesday, December 29, 2015

253. Meeting Rooms II ----------M !!!!!!!~~~~~~~~!!!!!!!!

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

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

A:

 核心点,就是先排序(先start,再end),再每次找一个room,尽量多的排meeting

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){
            if(a[0]==b[0])
                return a[1]<b[1];
            return a[0] < b[0];
        });
        // each round, add a table, then arrange the max possible conference on it
        int res = 0;        
        while(not intervals.empty()){
            vector<int> pre = intervals[0];
            res++;
            vector<vector<int>> nextRound;
            for(int i =1;i<intervals.size();i++){
                auto cur = intervals[i];
                if(cur[0] >= pre[1]){
                    pre = cur;
                }else{
                    nextRound.push_back(cur);
                }
            }
            intervals = nextRound;
        }
        return res;
    }
};

Mistakes:
竟然直接pass了, ╮(╯▽╰)╭





No comments:

Post a Comment