1094. 拼车 (opens new window)

1.差分数组

计算出某一个时刻的乘客人数，差分数组思想。起始位置加上上车人数，终点位置减去这一批下车人数，从而表征这一区间所有人数。

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        int[] cnt = new int[1001];
        for (int i = 0; i < trips.length; i++) {
            cnt[trips[i][1]] += trips[i][0];
            cnt[trips[i][2]] -= trips[i][0];
        }
        int space=0;
        for (int i = 0; i < cnt.length; i++) {
            space += cnt[i];
            if(space>capacity) return false;
        }
        return true;
    }
}

2.排序+优先级队列

先根据上车位置排序。然后维护一个下车点的小顶堆，及时计算扣减下车的人数。

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        Arrays.sort(trips, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[1] != o2[1]) return o1[1] - o2[1];
                return o1[2] - o2[2];
            }
        });
        int space = 0;
        PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        
        for (int i = 0; i < trips.length; i++) {
            //下车
            while (!queue.isEmpty() && queue.peek()[0] <= trips[i][1]) {
                int[] poll = queue.poll();
                space -= poll[1];
            }
            //上车
            queue.offer(new int[]{trips[i][2], trips[i][0]});
            space += trips[i][0];
            if(space>capacity) return false;
        }
        return true;
    }
}