### 题目

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.

For example, Given [[0, 30],[5, 10],[15, 20]], return 2.

### 贪婪算法

• Room 1: [1,3],[3,9],[9,12]
• Room 2: [2,5],[5,10],[10,14]

• Room 1: [[1,3],[5,10],[10,14]]
• Room 2: [[2,5],[9,12]
• Room 3: [[3,9]]

#### 用容器

public class Solution {
public int minMeetingRooms(Interval[] intervals) {
Arrays.sort(intervals, new Comparator<Interval>() {
public int compare(Interval a, Interval b) {
return a.start - b.start;
}
});
List<Interval> list = new ArrayList<>(Arrays.asList(intervals));
int count = 0;
while (!list.isEmpty()) {
int end = list.remove(0).end; count++; // create new timeline
Iterator<Interval> ite = list.iterator();
while (ite.hasNext()) {
Interval next = ite.next();
if (next.start >= end) { // add to current timeline
end = next.end;
ite.remove();
}
}
}
return count;
}
}

#### 直接在数组上改

public class Solution {
public int minMeetingRooms(Interval[] intervals) {
Arrays.sort(intervals, new Comparator<Interval>() {
public int compare(Interval a, Interval b) {
return a.start - b.start;
}
});
int count = 0;
for (int i = 0; i < intervals.length; i++) {
Interval ii = intervals[i];
if (ii == null) { continue; }
int end = ii.end;
intervals[i] = null; count++;
for (int j = i+1; j < intervals.length; j++) {
Interval ij = intervals[j];
if (intervals[j] == null) { continue; }
if (ij.start >= end) {
end = ij.end;
intervals[j] = null;
}
}
}
return count;
}
}

### Lazy Releasing法，用heap记录当前正在进行的会议的结束时间

#### 代码

public class Solution {
public int minMeetingRooms(Interval[] intervals) {
if (intervals.length == 0) { return 0; }
Arrays.sort(intervals, new Comparator<Interval>() {
public int compare(Interval a, Interval b) { return a.start - b.start; }
});
PriorityQueue<Integer> rooms = new PriorityQueue<>(intervals.length);
for (Interval meeting : intervals) {
Integer nextRoom = rooms.poll(); // give the room to be available soon
if (nextRoom == null) { rooms.add(meeting.end); continue; }
if (nextRoom > meeting.start) { rooms.offer(nextRoom); } // can not use this room
rooms.offer(meeting.end);
}
return rooms.size();
}
}

#### Lazy Releasing法的聪明解法，不需要heap

public class Solution {
public int minMeetingRooms(Interval[] intervals) {
int len = intervals.length;
if (len == 0) { return 0; }
int[] start = new int[len];
int[] end = new int[len];
for (int i = 0; i < len; i++) {
start[i] = intervals[i].start;
end[i] = intervals[i].end;
}
Arrays.sort(start);
Arrays.sort(end);
int rooms = 0;
for (int i = 0, j = 0; i < len; i++) {
if (start[i] < end[j]) {
rooms++;
} else {
j++;
}
}
return rooms;
}
}

|_____|
|______|
|________|
|_______|

||    ||                <- start time
|   |   |  |       <- end time

ab    cd
||    ||                <- start time
|   |   |  |       <- end time
1   2   3  4

+----------------------> a会议占据001会议室
|+---------------------> b会议占据002会议室
||    +----------------> c会议开始时，有一个会议室空出来。有可能是001号也可能是002号。
||    |+---------------> d会议占据003会议室
ab    cd
||    ||                <- start time
|   |   |  |       <- end time
1   2   3  4

### 更简单的 $O(n)$ 的算法

private class Solution extends Solution {
public int minMeetingRooms(Interval[] intervals) {
// get max array size
int size = 0;
for (Interval meeting : intervals) { // need a big array of size [max value in intervals]
size = Math.max(size,meeting.end);
}
// accumulate informations
int[] start = new int[size+1];
int[] end = new int[size+1];
for (Interval meeting : intervals) {
start[meeting.start]++;
end[meeting.end]--;
}
// collect result
int curr = 0, max = 0;
for (int i = 0; i <= size; i++) {
// end[i] rooms released at time (i), then start[i] new meetings ask for rooms
curr += start[i]; curr += end[i];
max = Math.max(max, curr);
}
return max;
}
}

#### 简化版

startend合并成一个数组。

private class Solution extends Solution {
public int minMeetingRooms(Interval[] intervals) {
// get max size
int size = 0;
for (Interval meeting : intervals) {
size = Math.max(size,meeting.end);
}
// accumulate informations
int count[] = new int[size+1];
for (Interval meeting : intervals) {
count[meeting.start]++;
count[meeting.end]--;
}
// get result
int max = 0, curr = 0;
for (int i = 0; i <= size; i++) {
curr += count[i];
max = Math.max(max,curr);
}
return max;
}
}