253. Meeting Rooms II

Leetcode Heap Greedy Sort

Given an array of meeting time intervals consisting of start and end times $[[s_1,e_1],[s_2,e_2],...], (s_i < e_i)$ , find the minimum number of conference rooms required.

Example:

Given intervals = [(0,30),(5,10),(15,20)], return 2.

分析¶

给定会议时间间隔，要求所需的最小的会议室数量。将会议时间间隔按照会议开始时间排序，如果后一个会议的开始时间小于上一个会议的结束时间，则需要多一个会议室。如果有 $k$ 个会议室，如果后一个会议的开始时间小于所有会议室的会议结束时间，则需要多一个会议室；如果不需要，则将会议安排到任意已经结束会议的会议室。时间复杂度为 $O(kn)$ ，其中 $n$ 为会议数量， $k$ 为需要的会议室数量。

public int minMeetingRooms(List<Interval> intervals) {
    intervals.sort(Comparator.comparing(o -> o.start));
    List<Integer> meetingRooms = new ArrayList<>();     // 每个会议室的会议结束时间
    meetingRooms.add(-1);
    for (Interval interval : intervals) {
        int i = 0;
        // 寻找任意一个已经结束会议的会议室
        while (i < meetingRooms.size() && meetingRooms.get(i) > interval.start) i++;
        // 如果没有，则增加一个会议室
        if (i == meetingRooms.size()) meetingRooms.add(interval.end);
        // 否则，将该会议安排到寻找到的会议室，并更新结束时间
        else meetingRooms.set(i, interval.end);
    }
    return meetingRooms.size();
}

也可以将会议安排到最早结束会议的会议室，时间复杂度为 $O(k^2n)$ .

public int minMeetingRooms(List<Interval> intervals) {
    if (intervals == null || intervals.size() == 0) return 0;
    intervals.sort(Comparator.comparing(o -> o.start));
    List<Integer> meetingRooms = new ArrayList<>();     // 每个会议室的会议结束时间
    meetingRooms.add(-1);
    for (Interval interval : intervals) {
        // min是最早结束会议的会议室
        int min = 0;
        // 寻找min
        for (int i = 0; i < meetingRooms.size(); i++)
            if (meetingRooms.get(i) < meetingRooms.get(min))  min = i;
        // 如果最早结束会议的会议室仍旧不能满足该会议的时间，则增加一个会议室
        if (meetingRooms.get(min) > interval.start)  meetingRooms.add(interval.end);
        // 否则，将该会议安排到寻找到的会议室，并更新结束时间
        else meetingRooms.set(min, interval.end);
    }
    return meetingRooms.size();
}

使用优先级队列保存会议室的结束时间，而不是数组，每次poll()会提取最早结束的会议室，优化了时间复杂度，时间复杂度为 $O(n\log n)$ .

public int minMeetingRooms(List<Interval> intervals) {
    if (intervals == null || intervals.size() == 0) return 0;
    intervals.sort(Comparator.comparing(o->o.start));
    PriorityQueue<Integer> queue = new PriorityQueue<>();
    int count = 1;
    queue.offer(intervals.get(0).end);
    for(int i = 1; i < intervals.size(); i++){
        if(intervals.get(i).start < queue.peek()) count++;
        else queue.poll();
        queue.offer(intervals.get(i).end);
    }
    return count;
}

下面是另一类方法扫描线算法：

扫描线（sweep line)：将区间在x轴上画出来，并用一条垂直于x轴的线作为扫描线从左至右扫描，会很容易得出答案，即与扫描线相交的区间的数量的最大值为所求答案。

sweep_line

但是在程序中我们怎样表示这种思想呢？

对所有点进行标记，区分起始点和终止点
对所有点进行排序
依次遍历每个点，遇到起始点+1，遇到终止点-1，并更新记录最大值

对所有点进行标记有几种方法

第一种方法是用两个一维数组来做，分别保存起始时间和结束时间，然后各自排序，定义结果变量minRooms和结束时间指针endpos，然后我们开始遍历，如果当前起始时间start[i]小于结束时间指针的时间ends[endpos]，则结果自增1，反之结束时间指针自增1，这样我们可以找出重叠的时间段，从而安排新的会议室，参见代码如下：

public int minMeetingRooms(List<Interval> intervals) {
    if (intervals == null || intervals.size() == 0) return 0;
    int[] starts = new int[intervals.size()];   // 保存会议开始时间
    int[] ends = new int[intervals.size()];     // 保存会议结束时间
    for (int i = 0; i < intervals.size(); i++) {
        starts[i] = intervals.get(i).start;
        ends[i] = intervals.get(i).end;
    }
    // 各自排序
    Arrays.sort(starts);
    Arrays.sort(ends);

    // 扫描线段
    int minRooms = 0, endpos = 0;
    for (int i = 0; i < intervals.size(); i++)
        if (starts[i] < ends[endpos]) minRooms++;
        else endpos++;
    return minRooms;  
}

一种更好的办法是，直接用+1表示开始时间点，用-1表示结束时间点，而不用分别在两个数组中存储。可以使用TreeMap自动实现分类。

public int minMeetingRooms(List<Interval> intervals) {
    if (intervals == null || intervals.size() == 0) return 0;
    TreeMap<Integer, Integer> map = new TreeMap<>();
    int minRooms = 0;           // 总共所需要的会议室
    int currentRooms = 0;       // 现在使用的会议室数量
    // 会议开始时间为1，结束时间为-1
    for (Interval interval : intervals) {
        map.put(interval.start, map.getOrDefault(interval.start, 0) + 1);
        map.put(interval.end, map.getOrDefault(interval.end, 0) - 1);
    }

    // 扫描
    for (int k : map.keySet()) {
        currentRooms += map.get(k);
        minRooms = Math.max(minRooms, currentRooms);
    }
    return minRooms; 
}