题目描述

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

算法1

sort + min-heap $O(n)$

时间复杂度

C++ 代码

    // 先sort，然后遍历所有 intervals，
    // 在当前 interval的开始时刻，结束可以结束的meetings，
    // 剩下的就是还在进行的meeting, 再加上当前meeting
    // 用 end time 的小顶堆 manage meetings，可以快速知道 在给定时刻，哪些meeting可以结束。
    // 这个题目 sort start 和 srot by [start, end) 效果一样

    int minMeetingRooms(vector<vector<int>>& intervals) {
        if(intervals.size()==0) return 0;

        sort(begin(intervals), end(intervals));

        int res = 1;
        priority_queue<int, vector<int>, greater<int>> pq;

        for(const auto& x : intervals) {
            while(pq.size() && pq.top() <= x[0]) pq.pop();   
            pq.push(x[1]);
            res = max(res, (int)pq.size());
        }
        return res;
    }

算法2

tree map $O(n)$

C++ 代码

    // map<int, int> : time -> num_meetings，即 时刻 -> 该时刻正在进行的meeting数量
    // 将所有meeting加入到map中，start 时刻+1，end 时刻-1
    // 在 tree map 里 key是有序的，扫描一遍，累加 num_meetings，最大值就是同时进行的meeting数量

    // 时间:   0  5   10  15  20  30
    // event: +1  +1  -1  +1  -1  -1
    // 累计   1   2   1   2   1   0

    int minMeetingRooms(vector<vector<int>>& xs) {
        int n = xs.size();
        if(n<=1) return n;

        map<int, int> m;

        for(auto& x : xs) {
            m[x[0]] ++;
            m[x[1]] --;
        }

        int res = 0, acc = 0;
        for(auto& kv : m) {
            acc += kv.second;
            res = max(res, acc);
        }
        return res;
    }