05 August 2008
Given an array of meeting time intervals ‘intervals’ where ‘intervals[i] = [starti, endi]’, return the minimum number of conference rooms required.
Example 1:
1
2
Input: [[0, 30],[5, 10],[15, 20]]
Output: 2
Example 2:
1
2
Input: [[7,10],[2,4]]
Output: 1
这道题是252的扩展，问最少需要多少个房间，如果同一时间有时间冲突，那就得安排不同的会议室。 这道题有以下解法
1）排序，把区间变成2个数组：start时间数组和end时间数组，各自排序，定义结果变量result和结束时间指针，然后开始遍历，如果当前起始时间小于结束时间指针的时间，则结果自增1，反之结束时间指针自增1（去往下一个结束时间指针，因为后面的起始时间不会再早于当前结束时间了），这样我们可以找出重叠的时间段，从而安排新的会议室；
2）TreeMap， 遍历intervals，对于起始时间，映射值自增1，对于结束时间，映射值自减1，然后定义结果变量curRoom，和房间数rooms，遍历TreeMap，时间从小到大，房间数每次加上映射值，然后更新结果，遇到起始时间，映射是正数，则房间数会增加，如果一个时间是一个会议的结束时间，也是另一个会议的开始时间，则映射值先减后加仍为0，并不用分配新的房间，而结束时间的映射值为负数更不会增加房间数；
3）最小堆minHeap，先按start排序，然后建立一个minHeap，堆顶元素是会议结束时间最早的区间，也就是end最小。开始遍历时间区间，如果堆不为空，且每次比较top元素的end时间和当前元素的start时间，如果 start >= end，说明该room可以释放出来并接下来被当前会议区间使用，这时候就poll堆中的首元素，再把当前区间压入堆，遍历完成后堆中元素的个数即为需要的会议室的个数，其实minHead就是按结束时间排序的最小堆，里面存需要多少个房间。
排序解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
* }
*/
class Solution {
public int minMeetingRooms(Interval[] intervals) {
if (intervals == null || intervals.length == 0) {
return 0;
}
int len = intervals.length;
int[] starts = new int[len];
int[] ends = new int[len];
int rooms = 0;
int endIndex = 0;
for (int i = 0; i < len; i++) {
starts[i] = intervals[i].start;
ends[i] = intervals[i].end;
}
Arrays.sort(starts);
Arrays.sort(ends);
for (int i = 0; i < len; i++) {
if (starts[i] < ends[endIndex]) {//有冲突，新的会议开始了而前面endIndex指向的会议还没结束
rooms++;
} else {//没冲突
endIndex++;
}
}
return rooms;
}
}
新的输入参数变了，是一个二维数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public int minMeetingRooms(int[][] intervals) {
if (intervals == null || intervals.length == 0) {
return 0;
}
int len = intervals.length;
int[] starts = new int[len];
int[] ends = new int[len];
int result = 0;
int endIndex = 0;
for (int i = 0; i < len; i++) { //头尾分别存上
starts[i] = intervals[i][0];
ends[i] = intervals[i][1];
}
Arrays.sort(starts);
Arrays.sort(ends);
for (int i = 0; i < len; i++) {
if (starts[i] < ends[endIndex]) { // 当前起始时间早于当前结束时间，安排房间+1
result++;
} else { // 去往下一个结束时间指针，因为排序后后面的起始时间不会再早于当前结束时间了
endIndex++;
}
}
return result;
}
}
TreeMap解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public int minMeetingRooms(int[][] intervals) {
TreeMap<Integer,Integer> rooms = new TreeMap<>();
for(int[] interval:intervals){
rooms.put(interval[0],rooms.getOrDefault(interval[0],0) + 1);
rooms.put(interval[1],rooms.getOrDefault(interval[1],0) - 1);
}
int maxRooms = 0;
int totalRooms = 0;
for(int room : rooms.values()){
totalRooms += room;
maxRooms = Math.max(maxRooms,totalRooms);
}
return maxRooms;
}
}
最小堆MinHeap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int minMeetingRooms(int[][] intervals) {
Arrays.sort(intervals, Comparator.comparingInt(i -> i[0]));
//priority queue is ordered by end schedules
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(q -> q[1]));
for (int[] interval : intervals) {
//if new input's start is later than priority queue's first end,
//priority queue could poll() !!!
if (!pq.isEmpty() && interval[0] >= pq.peek()[1]) {
pq.poll();
}
pq.add(interval);
}
return pq.size();
}
}