ORID 58 Meeting rooms II

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