Version: Next

253.会议室2

253. 会议室 II

难度 中等

给你一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，为避免会议冲突，同时要考虑充分利用会议室资源，请你计算至少需要多少间会议室，才能满足这些会议安排。

示例 1：

输入：intervals = [[0,30],[5,10],[15,20]]
输出：2

示例 2：

输入：intervals = [[7,10],[2,4]]
输出：1

提示：

  • 1 <= intervals.length <= 104
  • 0 <= starti < endi <= 106

最小堆法

  • 先排序
  • 存储会议的结束时间，那么堆顶就是当前即将结束的会议的结束时间
  • 遍历会议，将会议的 开始时间 与 堆顶 比较
    • 开始时间 < 堆顶：开辟新会议室，将当前会议的 结束时间 入堆
    • 开始时间 > 堆顶：说明之前有一个会议结束了，不开辟新会议室，加入当前会议结束时间，将堆顶弹出
  • 最终最小会议室数目就等于堆中元素数

最小堆实际上标记的是当前正在进行的会议，以及它们的结束时间，堆顶为最先结束的结束时间

  • 与堆顶比较操作的时间复杂度为 O(1)

image-20210423132651917

public int minMeetingRooms(int[][] intervals) {
if (intervals.length < 2) return 1;
// 按照会议的开始时间排序
Arrays.sort(intervals, (arr1, arr2) -> arr1[0] - arr2[0]);
// 最小堆 存放每一个会议的结束时间
PriorityQueue<Integer> heap = new PriorityQueue<>();
heap.add(intervals[0][1]);
for (int i = 1; i < intervals.length; i++) {
// 不为空，以当前开始时间 比较 堆顶，堆顶即最早结束时间
if (intervals[i][0] < heap.peek()) { // 在结束前就要开会
// 开辟新会议室，也就是当前值入堆
heap.add(intervals[i][1]);
} else {
heap.add(intervals[i][1]);
heap.poll();
}
}
return heap.size();
}
简化
public int minMeetingRooms(int[][] intervals) {
if (intervals.length < 2) return 1;
// 按照会议的开始时间排序
Arrays.sort(intervals, (arr1, arr2) -> arr1[0] - arr2[0]);
// 最小堆 存放每一个会议的结束时间
PriorityQueue<Integer> heap = new PriorityQueue<>();
heap.add(intervals[0][1]);
for (int i = 1; i < intervals.length; i++) {
heap.add(intervals[i][1]);
// 不为空，以当前开始时间 比较 堆顶，堆顶即最早结束时间
if (intervals[i][0] >= heap.peek())
heap.poll(); // 有会议开完了
}
return heap.size();
}

  • 时间复杂度 O(nlogn)

    • 排序 O(logn)
    • 添加、删除 O(logn)
    • 查看堆顶 O(1)

  • 空间复杂度 O(n)

分开排序法

  • 单独将会议的开始时间、会议的结束时间进行排序
  • 定义两个指针 beginIndex 遍历开始时间数组，endIndex 遍历结束时间数据，遍历开始时间数组
    • 当前开始时间 < 当前结束时间
      • 要开辟新会议室
      • beginIndex++
    • 当前开始时间 >= 当前结束时间
      • 说明有会议结束，不需要开辟新会议室
      • beginIndex++
      • endIndex++
public int minMeetingRooms(int[][] intervals) {
if (intervals.length < 2) return 1;
int[] begins = new int[intervals.length];
int[] ends = new int[intervals.length];
for (int i = 0; i < intervals.length; i++) {
begins[i] = intervals[i][0];
ends[i] = intervals[i][1];
}
// 排序
Arrays.sort(begins);
Arrays.sort(ends);
int bIndex = 0;
int eIndex = 0;
int rooms = 0;
while (bIndex < begins.length) {
if (begins[bIndex] < ends[eIndex]) rooms++;
else eIndex++;
bIndex++;
}
return rooms;
}
增强 for 循环写法
public int minMeetingRooms(int[][] intervals) {
if (intervals.length < 2) return 1;
int[] begins = new int[intervals.length];
int[] ends = new int[intervals.length];
for (int i = 0; i < intervals.length; i++) {
begins[i] = intervals[i][0];
ends[i] = intervals[i][1];
}
// 排序
Arrays.sort(begins);
Arrays.sort(ends);
int eIndex = 0;
int rooms = 0;
for (int begin : begins) {
if (begin < ends[eIndex]) rooms++;
else eIndex++;
}
return rooms;
}