Java 代码实现：判断是否能完成所有行程 - 拼车问题

Java 代码实现：判断是否能完成所有行程 - 拼车问题

一辆车有 capacity 个空座位。车只能向一个方向行驶（也就是说，不允许掉头或改变方向）。 给定整数 capacity 和一个数组 trips ， trip[i] = [numPassengersi, fromi, toi] 表示第 i 次旅行有 numPassengersi 乘客，接他们和放他们的位置分别是 fromi 和 toi 。这些位置是从汽车的初始位置向东的公里数。

当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false。

思路

模拟行驶过程，使用前缀和记录每个位置上车和下车的人数，判断每个位置上车和下车的人数是否超过容量。

Java 代码

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        int[] nums = new int[1001]; //记录每个位置上车和下车的人数
        for (int i = 0; i < trips.length; i++) {
            nums[trips[i][1]] += trips[i][0];
            nums[trips[i][2]] -= trips[i][0];
        }
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (sum > capacity) { //判断容量是否超限
                return false;
            }
        }
        return true;
    }
}