跳到主要内容

Meeting Rooms II

描述

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.

Example 1:

Input: [[0, 30],[5, 10],[15, 20]]
Output: 2

Example 2:

Input: [[7,10],[2,4]]
Output: 1

分析

首先将数组按照interval的开始时间排序,然后设置一个小根堆,用于存储的正在使用中的会议室,按结束时间排序,堆顶就是结束时间最小的interval。遍历数组,把一个一个的interval压入堆,每次压入之前,把新区间与堆顶的区间进行比较,如果新区间的开始时间大于堆顶的结束时间,说明堆顶的会议室已经结束,把它弹出,然后压入新区间。数组遍历结束后,堆的大小就是所需要的会议室数量。

// Meeting Rooms II
// Time Complexity: O(nlogn), Space Complexity: O(n)
class Solution {
public int minMeetingRooms(int[][] intervals) {
if (intervals.length == 0) return 0;
Arrays.sort(intervals,(int[] a, int[] b) ->a[0] - b[0]);

PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
pq.offer(intervals[0][1]);

for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] >= pq.peek()) pq.poll();
pq.add(intervals[i][1]);
}

return pq.size();
}
}

相关题目