美文网首页
ORID 58 Meeting rooms II

ORID 58 Meeting rooms II

作者: Wilbur_ | 来源:发表于2020-10-21 09:26 被阅读0次

今天每日一题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;
    }

相关文章

网友评论

      本文标题:ORID 58 Meeting rooms II

      本文链接:https://www.haomeiwen.com/subject/ndnhmktx.html