会议室 II
难度:
标签:
题目描述
代码结果
运行时间: 27 ms, 内存: 18.5 MB
/*
题目：253. 会议室 II
题目描述：
给你一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，请你计算至少需要多少间会议室，才能容纳所有会议。
题目思路：
1. 首先，将所有的会议按开始时间进行排序。
2. 使用一个最小堆（优先队列）来跟踪当前正在进行的会议的结束时间。
3. 遍历所有会议：
- 如果当前会议的开始时间大于堆顶的结束时间，说明有会议结束，可以腾出会议室，弹出堆顶。
- 将当前会议的结束时间加入堆中。
4. 最终堆的大小就是所需会议室的数量。
*/
import java.util.Arrays;
import java.util.PriorityQueue;
public class MeetingRoomsIIStream {
public int minMeetingRooms(int[][] intervals) {
if (intervals == null || intervals.length == 0) {
return 0;
}
// 按照会议的开始时间排序
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
// 使用最小堆存放会议的结束时间
PriorityQueue<Integer> pq = new PriorityQueue<>();
// Stream 处理会议室
Arrays.stream(intervals).forEach(interval -> {
// 如果当前会议的开始时间大于堆顶的结束时间，弹出堆顶
if (!pq.isEmpty() && interval[0] >= pq.peek()) {
pq.poll();
}
// 将当前会议的结束时间加入堆
pq.offer(interval[1]);
});
// 最终堆的大小就是所需会议室的数量
return pq.size();
}
}
解释
方法:
这个题解是使用优先队列（小根堆）来解决会议室安排问题。首先对会议时间区间按开始时间排序。然后遍历每个会议，对于当前遍历到的会议，如果优先队列不为空且队首元素小于等于当前会议的开始时间，说明队首的会议已经结束，可以弹出队首。接着将当前会议的结束时间加入优先队列。同时维护一个变量 ans 记录优先队列的最大长度，即需要的最多会议室数量。最后返回 ans 即可。
时间复杂度:
O(nlogn)
空间复杂度:
O(n)
代码细节讲解
🦆
代码中的`ans = max(ans, len(pq))`是如何确保能够准确计算出所需的最大会议室数量的？
▷相关问题
合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]] 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：
输入：intervals = [[1,4],[4,5]] 输出：[[1,5]] 解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。
提示：
1 <= intervals.length <= 104intervals[i].length == 20 <= starti <= endi <= 104
用最少数量的箭引爆气球
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。
给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。
示例 1：
输入：points = [[10,16],[2,8],[1,6],[7,12]] 输出：2 解释：气球可以用2支箭来爆破: -在x = 6处射出箭，击破气球[2,8]和[1,6]。 -在x = 11处发射箭，击破气球[10,16]和[7,12]。
示例 2：
输入：points = [[1,2],[3,4],[5,6],[7,8]] 输出：4 解释：每个气球需要射出一支箭，总共需要4支箭。
示例 3：
输入：points = [[1,2],[2,3],[3,4],[4,5]] 输出：2 解释：气球可以用2支箭来爆破: - 在x = 2处发射箭，击破气球[1,2]和[2,3]。 - 在x = 4处射出箭，击破气球[3,4]和[4,5]。
提示:
1 <= points.length <= 105points[i].length == 2-231 <= xstart < xend <= 231 - 1
拼车
车上最初有 capacity 个空座位。车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向）
给定整数 capacity 和一个数组 trips , trip[i] = [numPassengersi, fromi, toi] 表示第 i 次旅行有 numPassengersi 乘客，接他们和放他们的位置分别是 fromi 和 toi 。这些位置是从汽车的初始位置向东的公里数。
当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false。
示例 1：
输入：trips = [[2,1,5],[3,3,7]], capacity = 4 输出：false
示例 2：
输入：trips = [[2,1,5],[3,3,7]], capacity = 5 输出：true
提示：
1 <= trips.length <= 1000trips[i].length == 31 <= numPassengersi <= 1000 <= fromi < toi <= 10001 <= capacity <= 105