Render Calendar

EPI 13.5

Leetcode #253 Meeting Room II

Description:

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:

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

Idea:

1. 把所有edge的位置排序，如果edge位置相同，则右边的edge靠前
2. 相当于数longest valid parenthesis，这题的好处是parenthesis match，所以只用数数就行。

time O(nlogn)

Code:

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

 struct Interval {
     int start;
     int end;
     Interval() : start(0), end(0) {}
     Interval(int s, int e) : start(s), end(e) {}
 };

    int minMeetingRooms(vector<Interval>& intervals) {

        vector<pair<int, char>> sortedEnds;

        for(auto elem: intervals){
            sortedEnds.push_back(pair<int, char>(elem.start, 'l'));
            sortedEnds.push_back(pair<int, char>(elem.end, 'r'));
        }

        sort(sortedEnds.begin(), sortedEnds.end(), [](const pair<int, char>& a, const pair<int, char>& b)->bool {
            if(a.first!=b.first) 
                return a.first<b.first;
            else
                return a.second=='r'; });

        int maxCount=0;
        int count=0;
        for(auto elem: sortedEnds){
            if(elem.second == 'l'){
                count++;
                maxCount = max(maxCount, count);
            }
            else{
                count--;
            }
        }

        return maxCount; 
    }

int main(){
    vector<Interval> currSalary;
    currSalary.push_back(Interval(13,15));
    currSalary.push_back(Interval(1,13));

    cout<<minMeetingRooms(currSalary);
}