题目描述

给定一系列的会议时间间隔intervals，包括起始和结束时间[[s1,e1],[s2,e2],...] (si < ei)，找到所需的最小的会议室数量。

样例1

输入: intervals = [(0,30),(5,10),(15,20)]
输出: 2
解释:
需要两个会议室
会议室1:(0,30)
会议室2:(5,10),(15,20)

样例2

输入: intervals = [(2,7)]
输出: 1
解释:
只需要1个会议室就够了

https://www.lintcode.com/problem/meeting-rooms-ii/description

解法1

这种区间问题可以使用扫描线算法，我们将区间按照时间点排序，如果时间点相同，我们按照终点、起点顺序排序。这是因为在相同时间点上，当上一个会议结束后，该会议室就空出来了，在同一时间点的下一个会议就可以利用这个房间。例如时间段为{[1,5]、[5,10]}，其实只需要一个会议室就够了，因为当[1,5]的会议结束后，[5,10]就可以利用这个房间。

图1绘制了扫描线算法的执行流程，实际上我们并不需要按照最细的时间粒度来扫描，我们只需要扫描每个区间的起始点与结束点。因为只有在这些时间点上，需要的房间数量才会发生变化。上面提到过，遇到相同的时间点，我们应当将end排在start前面，因为当上一个会议结束就会空出一个会议室，在这个时间点的下一个会议就可以利用这个房间。

在实现上，我们将起始与终止的时间点用一维数组表示，第0个元素是时间点，第1个元素表示起始还是终止，用0表示end，用1表示start。这样我们可以实现Comparator来排序，首先对比时间点，当时间点相同对比起止。当时间点数组排好序后，我们顺序扫描时间点，用parallel变量表示该时刻需要使用的会议室数量。遇到起始点时parallel++；遇到结束点时parallel–，parallel出现的最大值就是所需的最小会议室数量。

全部代码如下，时间复杂度O(nlogn)，空间复杂度O(n)。

public class Solution {
    /**
     * @param intervals: an array of meeting time intervals
     * @return: if a person could attend all meetings
     */
    public int minMeetingRooms(List<Interval> intervals) {
        intervals.sort(Comparator.comparingInt(a -> a.start));

        List<int[]> timeAt = new ArrayList<>();
        for (Interval interval : intervals) {
            timeAt.add(new int[]{interval.start, 1});
            timeAt.add(new int[]{interval.end, 0});
        }

        timeAt.sort((a, b) -> {
            if (a[0] != b[0])
                return a[0] - b[0];
            return a[1] - b[1];
        });

        int res = 0, parallel = 0;

        for (int[] at : timeAt) {
            if (at[1] == 1)
                parallel++;
            else
                parallel--;
            res = Math.max(res, parallel);
        }

        return res;
    }
}