253. 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
题意：给一个二维数组，数组中的元素代表的是会议开始和结束的时间。 问安排下所有会议，所需要的最少的房间数。 这个题的重点在于如何找到可重复利用的房间。 需要想到，只要出现了结束时间，那么就代表有一个会议结束，就会有一个 room available， 所以我们需要把开始时间和结束时间按时间的顺序排序，扫一遍，遇到开始时间 +1 否则 -1， 记录最大值，就是结果。
代码 这个实现是用了 treemap
class Solution {
public int minMeetingRooms(Interval[] intervals) {
TreeMap<Integer, Integer> map = new TreeMap<>();
for(int i = 0; i < intervals.length; i++) {
int start = intervals[i].start;
if(!map.containsKey(start)) map.put(start, 0);
map.put(start, map.get(start) + 1);
int end = intervals[i].end;
if(!map.containsKey(end)) map.put(end, 0);
map.put(end, map.get(end) - 1);
}
int ret = 0;
int nums = 0;
while(!map.isEmpty()) {
nums += map.pollFirstEntry().getValue();
ret = Math.max(ret, nums);
}
return ret;
}
}
从分析我们可以开出，我们只要维护两个数组，一个代表开始时间的数组， 一个代表结束时间的数组。 这样虽然复杂度不变，但是速度依然会有提升。
class Solution {
public int minMeetingRooms(int[][] intervals) {
int n = intervals.length;
int[] start = new int[n];
int[] end = new int[n];
int i = 0;
for(int[] cur : intervals) {
start[i] = cur[0];
end[i] = cur[1];
i++;
}
Arrays.sort(start);
Arrays.sort(end);
i = 0;
int j = 0, room = 0, ret = 0;
while(i < start.length) {
if(start[i] < end[j]) {
room++;
i++;
} else {
room--;
j++;
}
//System.out.println(room);
ret = Math.max(ret, room);
}
return ret;
}
}