[leetcode] Meeting Rooms I && II


Meeting Rooms

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return false.

 

Meeting Rooms II

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.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return 2.

extract start point and end points from intervals.

Sort points by their time. If the time of two points are equal, arrange end point before start point.

traverse the sorted array,

if we meet a start point, count++, otherwise count–;

maxRooms stores the maximum value count ever appears.

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    int minMeetingRooms(vector<Interval>& intervals) {
        vector<pair<int, bool>> points;
        for(auto interval: intervals){
            points.push_back({interval.start, true});
            points.push_back({interval.end, false});
        }
        sort(points.begin(), points.end(), [](pair<int, bool>& a, pair<int, bool>& b){
            if(a.first < b.first){
                return true;
            }
            else if(a.first > b.first){
                return false;
            }
            else{
                return a.second == false; //end point is ordered before start point
            }
        });
        int count = 0;
        int maxRooms = 0;
        for(auto point: points){
            if(point.second == true){
                count++;
            }
            else{
                count--;
            }
            maxRooms = max(count, maxRooms);
        }
        return maxRooms;
    }
};

 

Leave a comment

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.