题目描述

给定一系列的会议时间间隔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 扫描线算法执行过程

图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;
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *