1094. Car Pooling

Car Pooling

题解

记$ tripk (z_k,s_k,t_k) x[0…n-1],y[0…n-1]x{sk}=z_k,y{t_k}=z_k$

设在位置时，车里的乘客的数量是，则

$$c_p=\sum_{i \le p} (x_i-y_i)$$

其中分别为在位置上车和下车的乘客数。

于是问题转化为，根据差分数组，恢复数组。

Java实现

class Solution{
    public boolean carPooling(int[][] trips,int capacity){
        int[] diff = new int[1001];
        for(int[] t:trips){
            diff[t[1]]+=t[0];
            diff[t[2]]-=t[0];
        }
        int total = 0;
        for(int c:diff){
            total+=c;
            if(total>capacity){
                return false;
            }
        }
        return true;
    }
}