253. 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.

Example 1:

Input: [[0, 30],[5, 10],[15, 20]]
Output: 2

Example 2:

Input: [[7,10],[2,4]]
Output: 1

// Treemap
int minMeetingRooms(vector<vector<int>>& intervals) { // time: O(nlogn); space: O(n)
    map<int, int> m;
    for (vector<int>& i : intervals) {
        ++m[i[0]];
        --m[i[1]];
    }
    int cur = 0, res = 0;
    for (auto& e : m) {
        cur += e.second;
        res = max(res, cur);
    }
    return res;
}

// Sort + Greedy
int minMeetingRooms(vector<vector<int>>& intervals) { // time: O(nlogn); space: O(n)
    if (intervals.empty()) return 0;
    sort(intervals.begin(), intervals.end());
    priority_queue<int, vector<int>, greater<int> > pq; // min heap
    pq.push(intervals[0][1]); // first end
    for (int i = 1; i < intervals.size(); ++i) {
        if (intervals[i][0] >= pq.top()) pq.pop();
        pq.push(intervals[i][1]);
    }
    return pq.size();
}

// Sort
int minMeetingRooms(vector<vector<int>>& intervals) { // time: O(nlogn); space: O(n)
    vector<pair<int, int> > v;
    for (const vector<int>& i : intervals) {
        v.push_back({i[0], 1});
        v.push_back({i[1], -1});
    }
    sort(v.begin(), v.end());
    int cur = 0, res = 0;
    for (pair<int, int>& p : v) {
        cur += p.second;
        res = max(res, cur);
    }
    return res;
}

252. Meeting Rooms