ORID 57. TreeMap Car Pooling

1094. Car Pooling
      这道题是今天的每日一题，我一开始是尝试着用priorityqueue想把每个trip按照路程起点和终点进行排序，然后看当前终点是否小于起点，如果小于的话就可以把第一批客人放下了，如果没有的话我就要看下面一趟trip的起点是否在当前路径的区间内，如果可以的话就可以car pool。但要检查capacity够不够，以此类推，知道把所有的trip走完之后如果中间没有违反情况，就返回true，如果有违反情况直接return false；

但是我的思路让代码里面有好多if else，然后有几个test case我发现怎么都过不去，最后看了一下别人的解答，我发现TreeMap这个数据结构在这里真的很好用。
TreeMap实际上就是sorted map，sorted based on key value.
这样的话你实际上是需要记录起点和终点就好了，把它们当作key，而value就是在这个起点或终点的时候乘坐的人数（起点人数为正，从capacity里面减掉当前人数，而终点人数为负，因为这样你用capacity减掉当前value的时候就可以恢复之前的capacity了。

最后用for loop把所有value加起来就好了，因为treemap本身就是排好序的，所以你就不用考虑如果之后路径起点比当前起点要低的情况。只要最后capacity大于0，就return true，else false；下面是代码

    public boolean carPooling(int[][] trips, int capacity) {
        Map<Integer, Integer> m = new TreeMap<>();
        for (int[] t : trips) {
            m.put(t[1], m.getOrDefault(t[1], 0) + t[0]);
            m.put(t[2], m.getOrDefault(t[2], 0) - t[0]);
        }
        for (int v : m.values()) {
            capacity -= v;
            if (capacity < 0) {
                return false;
            }
        }
        return true;
    }

时空复杂度

O（NlogN） M是起点终点的数量，N是trips有多少行
space O（N）