今天每日一题253. Meeting rooms II
用什么算法?
这道题首先要理解题意,为了用最少的房间来安排开会,你要先把每个会议开始的时间排序。然后按照每个会议结束的时间来进行判断需要多少个房间。TreeMap come to the rescue?
Treemap可以把每个输入的key按照顺序排好,所以这道题可以用这个数据结构。
其实之前有道题也有用到TreeMap的题目,只不过你自己对这个数据结构还是不够熟悉,我一开始没想到可以用TreeMap来解决这道题。
今天重新看了一下自己写的那道题的解释,发现这两道题的问题几乎就是一样的……都是问你在一个区间内,(start,end) 然后问你在一系列的区间中选择最小(或者最大)的可能,比如后面新来的区间(start1,end1)如果根当前区间冲突,那就要新开一个房间进行会议(meeting rooms)这道题,或者新来的区间根当前区间重合,我们车上的空间能否进行car pool(capacity-人数>0) (car pooling这道题)。
其实都是一个类型,你把他抽象化就都能用TreeMap来解了。car pooling 实际上就是meeting rooms 更复杂化的版本,meeting rooms 就把key 分为两种,start的value就为正,因为你要多加一个房间才能满足当前开会的要求,end key的value就为负,因为你当前会议已经结束了,所以value就是-1。
然后你把所有value加起来就可以了。
car pooling这道题则也是把key分为两种,start point 为负,因为你capacity是个正整数,代表你当前能够坐多少人。end point 为正,你把所有的start point 根end point排好序之后最后挨个把value加起来就可以了,如果期间capacity小于零,那就代表你不能完成这次car pool,return false就好了,如果能成功走完所有value,return true。
两道题的思想基本都一样。
不过我在讨论区看到一个答案也十分巧妙,他直接建了两个根interval一样长的数组,一个是start point,一个是end point,然后直接sort两个数组,最后用一个for loop 循环,如果当前start point 小于end point,res++,因为你需要新开一个房间来满足开会的要求,如果start <= end 那么就会有之前的房间空出来,所以endIndex++,这里endIndex是end[] 这个数组的指针,因为如果你有一个房间start point小于当前end, 那么这个end point就已经利用过了(这个房间空出来了),不过其实这跟TreeMap没什么区别,TreeMap其实就是把start point 根end point都排好序,只不过每个start point根end point对应的值(value)不一样,一个为正,一个为负。因为你最后要不就是看最小需要多少房间,要不就是看capacity够不够,所以都是对treemap的值进行操作。
那么 car pool 这道题是否也能够直接对start point end point进行排序?貌似不行,因为你需要记录start point根end point当前对应的乘客人数,单单对start point end point排序是不够的,因为没法记录你当前这趟车程载了多少乘客…… 好,下面是这方法的代码,来源
public int minMeetingRooms(Interval[] intervals) {
int[] starts = new int[intervals.length];
int[] ends = new int[intervals.length];
for(int i=0; i<intervals.length; i++) {
starts[i] = intervals[i].start;
ends[i] = intervals[i].end;
}
Arrays.sort(starts);
Arrays.sort(ends);
int rooms = 0;
int endsItr = 0;
for(int i=0; i<starts.length; i++) {
if(starts[i]<ends[endsItr])
rooms++;
else
endsItr++;
}
return rooms;
}
TreeMap的方法如下,这个方法更加广泛,能够用到很多类似的题目,我觉得熟练运用treemap更好。
public int minMeetingRooms(int[][] intervals) {
Map<Integer, Integer> map = new TreeMap<>();
for (int[] i : intervals) {
// record start time room number required
map.put(i[0], map.getOrDefault(i[0], 0) + 1);
// record end time room number required
map.put(i[1], map.getOrDefault(i[1], 0) - 1);
}
System.out.println(map);
int res = 0, cur = 0;
for (Integer val : map.values()) {
// you need min number of rooms. Before a meeting ends, record the max rooms needed
// for results
cur += val;
res = Math.max(res, cur);
}
return res;
}
网友评论