leetcode：253. 会议室 II 会员题
lintcode：919 · 会议室 II

题目

给你一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，为避免会议冲突，同时要考虑充分利用会议室资源，请你计算至少需要多少间会议室，才能满足这些会议安排。

示例：

输入：intervals = [[0,30],[5,10],[15,20]]
输出：2

输入：intervals = [[7,10],[2,4]]
输出：1

解答 & 代码

参考：扫描线技巧：安排会议室，但是这篇博客里没有解释代码含义。因此本文对代码进行了详细注释

本题是要计算同一时刻最多有多少会议在同时进行。
双指针解法：只需要注意什么时候开始会议、什么时候散会。将开始会议、散会的时间分为两个数组，通过滑动指针的方式，判断同时在开会的会议数量

class Solution {
public:
    public int minMeetingRooms(int[][] intervals) {
        int intervalsSize = intervals.size();
        // 开始开会时间数组，startTimeArr[i] 代表第 i 个会议的开始开会时间
        vector<int> startTimeArr(intervalsSize);
        // 散会时间数组，endTimeArr[i] 代表第 i 个会议的散会时间
        vector<int> endTimeArr(intervalsSize);
        for(int i = 0; i < intervalsSize; ++i)
        {
            startTimeArr[i] = intervals[i][0];
            endTimeArr[i] = intervals[i][1];
        }
        // 分别对开始开会时间数组、散会时间数组排序（从小到大，升序）
        sort(startTimeArr.begin(), startTimeArr.end());
        sort(endTimerArr.begin(), endTimeArr.end());
        // 双指针
        int i = 0;    // 当前时间已经开始开会的会议个数（包含已经结束的）
        int j = 0;    // 当前时间已经散会的会议个数
        int curMeettingCnt = 0;        // 当前时间同时在开会的会议数量，即当前同时使用的会议室数量
        int result = 0;                // 结果，即每个时间需要会议室数量的最大值
        while(i < intervalsSize && j < intervalsSize)
        {
            // startTimeArr[i] 代表下个开始开会会议的开始时间
            // endTimeArr[j] 代表下个散会会议的散会时间
            // 取两者中较小值，作为当前跳到的时间
            // 跳到下个开始开会会议的开始时间
            if(startTimeArr[i] < endTimeArr[j])
            {
                ++i;                // 当前时间已经开始开会的会议个数 +1
                ++curMeetingCnt;    // 当前时间同时在开会的会议数量 +1
            }
            // 跳到下个散会会议的散会时间
            else
            {
                ++j;                // 当前时间已经散会的会议个数 +1
                --curMeetingCnt;    // 当前时间同时在开会的会议数量 -1
            }
            // 将当前使用的会议室数量和全局最大值比较，更新 result
            result = max(result, curMeetingCnt);
        }
        return result;
    }
};

复杂度分析：数组 intervals 长为 N，即会议总数为 N

时间复杂度 O(N logN)：数组排序
空间复杂度 O(N)：

litcode 解答：

/**
 * Definition of Interval:
 * class Interval {
 * public:
 *     int start, end;
 *     Interval(int start, int end) {
 *         this->start = start;
 *         this->end = end;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param intervals: an array of meeting time intervals
     * @return: the minimum number of conference rooms required
     */
    int minMeetingRooms(vector<Interval> &intervals) {
        int len = intervals.size();
        vector<int> startTimes(len);    // 开始会议时间数组
        vector<int> endTimes(len);        // 结束会议时间数组
        for(int i = 0; i < len; ++i)
        {
            startTimes[i] = intervals[i].start;
            endTimes[i] = intervals[i].end;
        }
        // 分别对两个数组进行排序
        sort(startTimes.begin(), startTimes.end());
        sort(endTimes.begin(), endTimes.end());
        int result = 0;     // 最多同时开会的会议数量，即最小需要的会议室数量
        int cnt = 0;        // 当前同时开会的会议数量
        // 双指针遍历（每次跳到最近开始会议 or 结束会议的时间）
        int startIdx = 0;
        int endIdx = 0;
        while(startIdx < len)
        {
            if(startTimes[startIdx] < endTimes[endIdx])    // 开始一个会议
            {
                ++cnt;                                    // 当前同时开会的会议数量 +1
                result = max(result, cnt);                // 更新答案
                ++startIdx;
            }
            else                                        // 结束一个会议
            {
                --cnt;                                    // 当前同时开会的会议数量 -1
                ++endIdx;
            }
        }
        return result;
    }
};

执行结果：

执行结果：通过
执行用时：41 ms, 在所有 C++ 提交中击败了 83.20% 的用户
内存消耗：2.29 MB, 在所有 C++ 提交中击败了 83.20% 的用户

hot 100

[中等] 253. 会议室 II

题目

解答 & 代码