Docs

Appearance

21 安排会议室：如何利用多种方法安排会议室？ ​

本讲是一题多解模块的最后一讲，之所以安排这一讲，是因为通常情况下，一道算法题目有多种的解法。我们与别人交流时，大家的思路和解题方法可能不同，每个人写出来的代码差异巨大。那么这些不同的正确解法，可以理解成"一题多解"吗？换句话说，你能分清什么是真正的"多解"，什么是"伪多解"吗？

通过这些"伪多解"，有助于我们看透题目的本质，从而掌握核心知识点，同时也可以降低我们需要理解和记忆的知识量。

所以，在本讲，你将掌握以下三种思考方法：

  • 如何通过"多解"看透知识点的本质（分清"伪多解""真多解"）？

  • 如何用多种技巧满足题目要求？

  • 如何深挖题目特点，达到一题多解的目标？

题目 ​

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

输入：会议时间表 [[0, 30],[5, 10],[15, 20]]

输出：最少需要的会议室数量 2

注意：如果有两个会议 [6,8] 和 [8,10]，我们认为这两个会议不冲突。

特点 1：时间分布 ​

拿到这个题时，我们要特别注意一点：

如果有两个会议，其中一个会议结束于时间点x，下一个会议同时从时间点y 开始，这两个会议可以用同一个会议室。也就是说，这两个时间段并不重合（虽然在时间点 x 相接）。

我们从时间点出发来考虑这个问题，有以下 3 种情况。

情况 1：需 1 个会议室 ​

首先我们考虑一种简单的情况，假设会议与会议之间均没有重合的情况。比如输入如下：

intervals=[0,1],[1,2],[2, 3]

在下图中，x 轴表示会议的时间表，y 轴表示将哪些会议放在哪个会议室，蓝色、橘色和红色分别表示不同的会议。

在这种情况下，每个时间点只可以被染上一种颜色，时间衔接得非常好，此时只需要一个会议室。接下来我们再看一下衔接得不那么好的情况。

在这种情况下，每个时间点只可以被染上一种颜色，或者没有染上颜色，同样此时最多也只需要一个会议室。

不过，我们还需要处理一种很麻烦的情况，此时 [6, 8] 和 [8, 10] 两个会议的时间点都会将时间点 8 进行染色。那岂不是时间点 8 会有两种颜色？针对这种情况，我们在染色的时候，可以做一点更正。

针对会议时间[start,end]染色时，只需要渲染[start,end)，不需要将end点进行染色。

此时，即可满足：

区间 [6,8)与区间[8,10)不相交。

并且，我们不需要再对这种前后时间相接的情况做特殊判断。

情况 2：需 2 个会议室 ​

前面我们考虑的都是没有重合的情况，接下来，再看一下两个会议室 [0, 2) 和 [1, 4) 有重合的情况。

此时，只需要对 [0, 2) 和区间 [1, 4) 进行染色。我们发现，如果在时刻 1画一条竖线，会分别遇到两种颜色：蓝色和红色。

情况 3：需多个会议室 ​

前面考虑了需要 1 个和 2 个会议室的情况，接下来我们看一下稍微复杂一点的场景。

通过画图可以发现规律，y 轴的会议室的数目与某个点染色的次数相关。那么，我们可以把这个题转换为一个更加容易理解的题目：

给定一个数组A[]，再给定一系列区间[start, end)，我们将此区间中A[start...end)都加上1。最后求数组 A[] 中的最大值。

差分数组 ​

差分数组是一种求解区间累加的有效手段。我们先考虑只有一个区间 [start, end) 的情况。

一种暴力的写法是下面这样：

java
// 给定数组A[]已经初始化为0
// 处理一个区间的情况
for (int i = start; i < end; i++) {
  A[i]++;
}
// 这里是累加之后的A[]数组

我们可以通过画图表示操作后的结果，如下图所示：

如果我们只关心每个时间点的涨幅与跌幅，那么可以对每个点进行标注，如下图所示：

你可以按照如下操作，得到任意时刻的累计值（解析在注释里）：

java
// 给定数组A[]已初始化全为0
// 处理一个区间
A[start] += 1;
A[end] -= 1;
// 最后求前缀和，得到任意时刻的值
pre = 0;
for (int i = start; i < end; i++) {
  pre += A[i];
  A[i] += pre;
}

无论是一个区间还是多个区间，我们都可以参考上述方式进行处理，代码如下（解析在注释里）：

java
// 给定数组A[]已初始化全为0
for (Interval range: intervals) {
  A[range.start] += 1;
  A[range.end] -= 1;
}
// 最后求前缀和，得到任意时刻的值
pre = 0;
for (int i = start; i < end; i++) {
  pre += A[i];
  A[i] += pre;
}

基于这个知识点，我还给你留了一个练习题。

练习题 1 ：假设你有一个长度为n的数组，数组的所有元素初始化为0，并且给定k个更新操作。每个更新操作表示为一个三元组：[startIndex, endIndex, inc]。这个更新操作给子数组A[start``I``ndex````... endIndex]（包括startIndex和endIndex）中的每一个元素增加inc。返回执行k个更新操作后的新数组。

代码：Java/C++/Python

改进 1： 哈希表 ​

如果我们直接使用差分数组，好像无法直接破解这个题，因为题目中并没有约定所有整数的范围。比如，如果给定的某个会议时间段是 [0, 10000000000]，就无法直接申请 A[10000000000] 这么大的数组。

因此，我们还需要对差分数组做一点改进：可以尝试用哈希表来表示数组。

改进 2：范围 ​

在标准的差分数组中，我们需要返回的是一个操作之后的数组，也就是求出每一个 A[i] 的值。但是在这个题中，只需要拿到数组的最大值就可以了。因此，我们也没有必要求出每一个 A[i] 的值。

综上，可以写出基于差分数组的改进的代码如下（解析在注释里）：

java
class Counter extends HashMap<Integer, Integer> {
    public int get(Integer k) {
        return containsKey(k) ? super.get(k) : 0;
    }
    public void add(Integer k, int v) {
        put(k, get(k) + v);
    }
}
public class Solution {
  /**
   * @param intervals: an array of meeting time intervals
   * @return: the minimum number of conference rooms required
   */
  public int minMeetingRooms(List<Interval> intervals) {
      // Write your code here
      // 利用Hash表生成A[]数组
      Counter A = new Counter();
      for (Interval range: intervals) {
        final int start = range.start;
        final int end = range.end;
        A.add(start, 1);
        A.add(end, -1);
      }
      List<Integer> idx = new ArrayList<>(A.keySet());
      Collections.sort(idx);
      int pre = 0;
      int ans = 0;
      for (Integer i: idx) {
        pre += A.get(i);
        ans = Math.max(ans, pre);
      }
      return ans;
  }
}

代码：Java/C++/Python

复杂度分析：时间复杂度为 O(NlgN)，空间复杂度为 O(N)。

我们发现，这个题目的考点就是在差分数组上的两点变化：

  • 利用哈希表表示数组；

  • 由于只需要求最大值，因此我们求出区间端点的值就可以了。

接下来，我们来看另外一种思路。

特点 2：变招 1 ​

我们继续讨论一下差分数组的解法。在本题中，我们需要的并不是一个标准的差分解法。经过分析之后，实际上只需要处理以下情况：

  • 给定区间 [start, end)；

  • 只需要遇到 start 时 +1；

  • 只需要遇到 end时 -1；

  • 然后再利用累计求和的方式计算每个位置的值。

在前面我们用了哈希数组的办法，那么，哈希数组就是必需的吗？

由于我们并不像差分数组一样返回操作之后的整个数组，而是返回最大值。因此只需要经过以下两步，就可以得到最大值。

  • Step 1. 将所有的下标放到一个数组中，并且进行排序。

  • Step 2. 从头倒尾遍历下标，如果遇到区间的起始点，那么 +1；如果遇到区间的终点，那么 -1。

操作伪代码如下：

java
item = [收集了所有的下标]
sort(item)
ans = 0
pre = 0
for 坐标 in item:
    if 坐标是区间的起始点:
        pre += 1
    else:
        pre -= 1
    ans = max(ans, pre)
return ans

这里还有两个地方需要处理：

1 ) 如何判断经过排序之后的下标，是区间的终点还是一个区间的起始点？

解决方法：在放到 item 里面的时候，我们可以将起始点设置为正值，终点设置为负值。

2 ）如果经过排序之后的下标分了正负，那么一个区间的终点将会位于 x 轴的负半轴，起始点位于 x 轴的正半轴，这并没有按照原本的坐标排序。

解决方法：排序时，我们只需要按照下标的绝对值排序即可。

基于这样的处理技巧，可以写出代码如下：

java
public class Solution {
  /**
   * @param intervals: an array of meeting time intervals
   * @return: the minimum number of conference rooms required
   */
  public int minMeetingRooms(List<Interval> intervals) {
    List<Integer> item = new ArrayList<>();
    for (Interval range: intervals) {
      item.add(range.start);
      item.add(0 - range.end);
    }
    Collections.sort(item, new Comparator<Integer>() {
        public int compare(Integer a, Integer b) {
          return Math.abs(a) - Math.abs(b);
        }
    });
    int ans = 0;
    int pre = 0;
    for (int i = 0; i < item.size(); i++) {
      if (item.get(i) >= 0) {
        pre++;
      } else {
        pre--;
      }
      ans = Math.max(ans, pre);
    }
    return ans;
  }
}

代码：Java/C++/Python

复杂度分析：时间复杂度为 O(NlgN)，空间复杂度为 O(N)。

在这里，我们已经快找不到差分数组的影子了，但是本质上还是基于差分数组进行求解。那么，还有其他的解法吗？

特点 3：变招 2 ​

前面在处理区间的时候：是将所有区间的起始点标记为非负，区间的终点标记为负数；排序时按照绝对值进行排序。然后再利用差分数组的核心思想：遇到区间的起始点 +1；遇到区间的终点 -1。

那么还有没有其他的招法呢？我们再认真地研究一下这个题目，不难发现，破题的关键就在两处条件：

  1. 需要将所有的坐标排序，并且需要知道每个坐标是属于一个区间的起始点还是终点。即顺序遍历坐标，知道每个坐标是起始点还是终点；

  2. 利用差分数组的核心思想，然后求出最大值。

根据条件 2，我们已知可以利用差分数组的思路，那么条件 1 这里还可以用别的方法吗？下面我们尝试完成条件 1 。

首先将所有区间的起始点坐标放到 starts 数组中，将所有区间的终点坐标放到 end 数组中。然后，再将 starts 和 end 采用合并排序的方法进行合并（注意，此时我们不是直接使用合并排序，准确来说是使用合并排序中的合并的技巧）。

此时，我们可以达成条件 1 的两个目的：

  • 顺序遍历每个坐标；

  • 知道每个坐标是区间起始坐标，还是终点坐标。

伪代码如下：

java
starts = [...区间的起始点...]
ends = [...区间的终点...]
sort(start);
sort(ends);
slen = len(starts)
elen = len(ends)
i = 0
j = 0
while i < slen || j < elen:
    if j >= elen || i < slen:
        遍历到了start[i]；并且我们知道这个坐标是区间的起始点
    else:
        遍历到了end[i]；并且我们知道这个坐标是区间的终点

基于这样的思想，再加上我们的差分核心思路，那么就可以写出如下代码了（解析在注释里）：

java

public class Solution {
    /**
     * @param intervals: an array of meeting time intervals
     * @return: the minimum number of conference rooms required
     */
    public int minMeetingRooms(List<Interval> intervals) {
        // Write your code here
        final int N = intervals == null ? 0 : intervals.size();
        int[] start = new int[N];
        int[] end = new int[N];
        int i = 0;
        for (Interval range: intervals) {
          start[i] = range.start;
          end[i] = range.end;
          i++;
        }
        Arrays.sort(start);
        Arrays.sort(end);
        i = 0;
        int j = 0;
        int pre = 0;
        int ans = 0;
        while (i < N || j < N) {
          if (j >= N || i < N && start[i] < end[j]) {
            // 是个坐标的起始点
            pre++;
            i++;
          } else {
            // 是个坐标的终点
            pre--;
            j++;
          }
          ans = Math.max(ans, pre);
        }
        return ans;
    }
}

代码：Java/C++/Python

复杂度分析：时间复杂度为 O(NlgN)，空间复杂度为O(N)。

接下来，我们再看看有没有其他的解法。

特点 4：最少 ​

再回到原始题目，要想会议室最少，那么我们在拿到一个 meeting = [start,end] 的时候，尽量不去开新的会议室，而是选择一个已有会议结束时间<= start 的会议室开会。

要做到这一点，我们需要记录每个会议室的结束时间；当给定 meeting = [start,end] 的时候，就需要找到一个 <= start 的会议室提供给这个 meeting使用。

到这里，不知道你是否想起了我们在《03 | 优先级队列：堆与优先级队列，筛选最优元素》中介绍的"例 3"。我们可以把会议室也放到优先级队列中，每次总是取出结束时间最早的会议室。

由于给定的所有的 meeting 并没有排好序。因此，我们还需要做一点预处理------对 meeting进行排序。此时你还会面临一个问题，在排序的时候，meeting有 [start,end]，那么应该按照 start 值来排序，还是按照 end 来排序呢？

答案是按照 start 值来排序。因为我们在选择会议室的时候，需要两个输入，分别是 meeting 的开始时间 start 和会议室的结束时间。

基于这样的思想，我们就可以写出如下的代码（解析在注释里）：

java

public class Solution {
  public int minMeetingRooms(List<Interval> intervals) {
      final int N = intervals == null ? 0 : intervals.size();
      
      // 把所有的会议时间段都按start来排序
      Collections.sort(intervals, new Comparator<Interval>() {
        public int compare(Interval a, Interval b) {
          return a.start - b.start;
        }
      });
      
      // 这里要按照会议室的结束时间来排序
      Queue<Integer> meetingRooms = 
          new PriorityQueue<>((v1, v2) -> v1 - v2);
          
      for (Interval meeting : intervals) {
        if (!meetingRooms.isEmpty() &&
              meetingRooms.peek() <= meeting.start) {
              
          // 我们需要把这个会议室的结束时间修改一下
          // 当然，优先级队列里面是不好直接修改元素值的
          // 那我们只能采用先出队，再把当前会议结束时间入队的方式
          meetingRooms.poll();
          meetingRooms.add(meeting.end);
        } else {
          // 如果找不到会议室，那么新开一间
          // 标记其结束时间
          meetingRooms.add(meeting.end);
        }
      }
      return meetingRooms.size();
  }
}

代码：Java/C++/Python

复杂度分析：时间复杂度为O(NlgN)，空间复杂度为 O(N)。

总结 ​

最后，我将本讲用到的知识整理成在一张思维导图中，方便你复习。

通过总结我们发现，这个题目的核心解法实际上只有两种，但是基于差分方法又出现了三种"伪多解"的做法，我们一一进行了分析，透过代码，相信你也学会了如何运用多种技巧来满足题目的条件。

当然，在面试中，如果你遇到这道题之后，面试官有可能还会深入地问你一些问题，比如下面这道一个思考题。

题目仍然不变，要求输出最少会议室的个数，并且还要输出每个会议室里面召开哪些会议。

输入：会议时间表[[0,30],[5,10],[15,20]]

输出：最少需要的会议室数量 2，[[0,30]] 放到会议室 1，[[5,10], [15,20]] 放到会议室 2。

代码：Java/C++/Python

你可以自己尝试求解这道题目，把答案写在留言区，我们一起讨论。关于这道会议室的题目就介绍到这里。接下来，下一讲介绍"22|数据结构模板：如何让解题变成搭积木？"，让我们继续前进。