1094. 拼车 Medium

车上最初有 capacity 个空座位。车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向）

给定整数 capacity 和一个数组 trips , trip[i] = [numPassengers_i, from_i, to_i] 表示第 i 次旅行有 numPassengers_i 乘客，接他们和放他们的位置分别是 from_i 和 to_i 。这些位置是从汽车的初始位置向东的公里数。

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

示例 1:
输入：trips = [[2,1,5],[3,3,7]], capacity = 4
输出：false

示例 2:
输入：trips = [[2,1,5],[3,3,7]], capacity = 5
输出：true

解题思路

输入：一个二维数组 trips,里面每个子数组代表第 i 段路程中的 [乘客数, 上车位置, 下车位置]

输出：判断能否在所有行程中接送完所有乘客

本题属于一维差分问题。

我们首先要知道总共的路程范围是 [0, 1000]

我们可以定义一个差分数组 diff = [0] * 1001，这里是从 0 到 1000 所以有 1001 个数

然后我们遍历每段旅程，并在每个区间的开始时 +乘客数，结束时 -乘客数

我们可以得到这样一个差分数组 [...2,0,0,0,-2,...6,0,0,-6...]

然后遍历这个差分数组，当发现这个点 > 0 则说明这个区间开始有乘客上车了，当下次遇到 < 0 的时候说明这几个乘客下车了

然后判断当位置不够的时候就说明还有乘客没到终点而又有新的乘客要上来，此时就可以直接返回 false

最后遍历完就说明所有乘客都达到指定地点，返回 true

代码实现

python

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        # 差分数组，最多只有 0~1000 公里
        diff = [0] * 1001

        # 使用差分数组记录每段路程中上下车人数的变化
        for num_passengers, start, end in trips:
            diff[start] += num_passengers     # 起点上车
            diff[end] -= num_passengers       # 终点下车

        # passengers 用于记录当前车上乘客数（通过前缀和恢复）
        passengers = 0
        for i in range(1001):
            passengers += diff[i]  # 累加当前站点的乘客变化量
            if passengers > capacity:
                return False       # 如果超载，立即返回 False

        return True  # 所有站点都未超载，返回 True

javascript

/**
 * @param {number[][]} trips
 * @param {number} capacity
 * @return {boolean}
 */
const carPooling = function(trips, capacity) {
    const diff = Array(1001).fill(0);

    for (let [np, start, end] of trips) {
        diff[start] += np;
        diff[end] -= np;
    }

    let passengers = 0;
    for (let i = 0; i < 1001; i++) {
        passengers += diff[i];
        if (passengers > capacity) 
            return false;
    }

    return true;
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

链接

1094 国际版

1094 中文版