1094. Car Pooling (差分

T: O(1001)

S: O(1001)

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        int[] diff = new int[1001];
        for (int[] trip : trips) {
            int pas = trip[0];
            int start = trip[1]; 
            int end = trip[2] - 1; // at trip[1] 下車
            diff[start] += pas;
            if (end + 1 < 1001) {
                diff[end+1] -= pas;
            }
        }
        int[] result = new int[1001];
        result[0] = diff[0];
        for (int i = 1; i < 1001; i++) {
            result[i] = result[i-1] + diff[i];
        } // 不能在這裡比, index 0 會比不到
        
        for (int i = 0; i < 1001; i++) {
            if (result[i] > capacity) {
                return false;
            }
        }
        return true;
    }
}