读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
| LeetCode | 力扣 | 难度 |
|---|---|---|
| 253. Meeting Rooms II🔒 | 253. 会议室 II🔒 | 🟠 |
之前面试，被问到一道非常经典且非常实用的算法题目：会议室安排问题。
力扣上类似的问题是会员题目，你可能没办法做，但对于这种经典的算法题，掌握思路还是必要的。
先说下题目，力扣第 253 题「会议室 II」：
给你输入若干形如 [begin, end] 的区间，代表若干会议的开始时间和结束时间，请你计算至少需要申请多少间会议室。
函数签名如下：
// 返回需要申请的会议室数量
int minMeetingRooms(int[][] meetings);
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。
// 返回需要申请的会议室数量
int minMeetingRooms(vector<vector<int>>& meetings);
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。
# 返回需要申请的会议室数量
def minMeetingRooms(meetings: List[List[int]]) -> int:
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。
// 返回需要申请的会议室数量
func minMeetingRooms(meetings [][]int) int {
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。
/**
* 返回需要申请的会议室数量
* @param {number[][]} meetings
* @return {number}
*/
var minMeetingRooms = function(meetings) {
// function body goes here
};
比如给你输入 meetings = [[0,30],[5,10],[15,20]]，算法应该返回 2，因为后两个会议和第一个会议时间是冲突的，至少申请两个会议室才能让所有会议顺利进行。
如果会议之间的时间有重叠，那就得额外申请会议室来开会，想求至少需要多少间会议室，就是让你计算同一时刻最多有多少会议在同时进行。
换句话说，如果把每个会议的起始时间看做一个线段区间，那么题目就是让你求最多有几个重叠区间，仅此而已。
我们之前也学习过区间相关的算法，如果你对 差分数组技巧 有印象，应该首先能想到用那个技巧来解决这个题。
这道题相当于是说，给你一个原本全是 0 的数组，然后给你若干区间，让你对每个区间中的元素都加 1，问你最后整个数组中的最大值是多少。这就是经典的差分数组实用场景对吧，直接套用前文给的 Difference 类就可以解决这个问题了。
但是差分数组技巧有一个问题，就是你必须把那个全是 0 的初始数组构造出来。由于我们用数组的索引表示时间，所以这个数组的长度取决于时间区间的最大值。
比如输入 meetings = [[0,30],[5,10],[15,20]]，那么你得构造一个长度为 30 的数组。那如果输入 meetings = [[0,30],[5,10],[10^8,10^9]]，这样的话你就得构造一个长度为 10^9 的数组，这显然是有问题的。不过这道题给的数据规模是时间的取值最多为 10^6，不算是特别大，用差分数组的方法应该可以通过。
但本文再教你另外的一个处理区间的技巧，不用构造这么大的数组，也能巧妙解决这个问题。
题目延伸
我们之前写过很多区间调度相关的文章，这里就顺便帮大家梳理一下这类问题的思路：
第一个场景，假设现在只有一个会议室，还有若干会议，你如何将尽可能多的会议安排到这个会议室里？
这个问题需要将这些会议（区间）按结束时间（右端点）排序，然后进行处理，详见前文 贪心算法做时间管理。
第二个场景，给你若干较短的视频片段，和一个较长的视频片段，请你从较短的片段中尽可能少地挑出一些片段，拼接出较长的这个片段。
这个问题需要将这些视频片段（区间）按开始时间（左端点）排序，然后进行处理，详见后文 剪视频剪出一个贪心算法。
第三个场景，给你若干区间，其中可能有些区间比较短，被其他区间完全覆盖住了，请你删除这些被覆盖的区间。
这个问题需要将这些区间按左端点排序，然后就能找到并删除那些被完全覆盖的区间了，详见后文 删除覆盖区间。
第四个场景，给你若干区间，请你将所有有重叠部分的区间进行合并。
这个问题需要将这些区间按左端点排序，方便找出存在重叠的区间，详见后文 合并重叠区间。
第五个场景，有两个部门同时预约了同一个会议室的若干时间段，请你计算会议室的冲突时段。
这个问题就是给你两组区间列表，请你找出这两组区间的交集，这需要你将这些区间按左端点排序，详见后文 区间交集问题。
第六个场景，假设现在只有一个会议室，还有若干会议，如何安排会议才能使这个会议室的闲置时间最少？
这个问题需要动动脑筋，说白了这就是个 0-1 背包问题的变形：
会议室可以看做一个背包，每个会议可以看做一个物品，物品的价值就是会议的时长，请问你如何选择物品（会议）才能最大化背包中的价值（会议室的使用时长）？
当然，这里背包的约束不是一个最大重量，而是各个物品（会议）不能互相冲突。把各个会议按照结束时间进行排序，然后参考前文 0-1 背包问题详解 的思路和 TreeMap 即可解决。
力扣第 1235 题「规划兼职工作」就是类似的题目，我在插件思路中给出了详细的解答，你可以安装我的 Chrome 插件 去查看，我在这里就不花费篇幅了。
第七个场景，就是本文想讲的场景，给你若干会议，让你最小化申请会议室的数量。
好了，举例了这么多，来看看今天的这个问题如何解决。