Question

1094. 拼车

English Version

题目描述

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

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

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

 

示例 1：

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

示例 2：

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

 

提示：

• 1 <= trips.length <= 1000
• trips[i].length == 3
• 1 <= numPassengersi <= 100
• 0 <= fromi < toi <= 1000
• 1 <= capacity <= 105

解法

方法一：差分数组

我们可以利用差分数组的思想，将每个行程的乘客数加到起点，减去终点，最后我们只需要判断差分数组的前缀和是否都不大于车的最大载客量即可。

时间复杂度 $O(n)$，空间复杂度 $O(M)$。其中 $n$ 是行程数，而 $M$ 是行程中最大的终点，本题中 $M \le 1000$。

class Solution:
  def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
    mx = max(e[2] for e in trips)
    d = [0] * (mx + 1)
    for x, f, t in trips:
      d[f] += x
      d[t] -= x
    return all(s <= capacity for s in accumulate(d))

class Solution {
  public boolean carPooling(int[][] trips, int capacity) {
    int[] d = new int[1001];
    for (var trip : trips) {
      int x = trip[0], f = trip[1], t = trip[2];
      d[f] += x;
      d[t] -= x;
    }
    int s = 0;
    for (int x : d) {
      s += x;
      if (s > capacity) {
        return false;
      }
    }
    return true;
  }
}

class Solution {
public:
  bool carPooling(vector<vector<int>>& trips, int capacity) {
    int d[1001]{};
    for (auto& trip : trips) {
      int x = trip[0], f = trip[1], t = trip[2];
      d[f] += x;
      d[t] -= x;
    }
    int s = 0;
    for (int x : d) {
      s += x;
      if (s > capacity) {
        return false;
      }
    }
    return true;
  }
};

func carPooling(trips [][]int, capacity int) bool {
  d := [1001]int{}
  for _, trip := range trips {
    x, f, t := trip[0], trip[1], trip[2]
    d[f] += x
    d[t] -= x
  }
  s := 0
  for _, x := range d {
    s += x
    if s > capacity {
      return false
    }
  }
  return true
}

function carPooling(trips: number[][], capacity: number): boolean {
  const mx = Math.max(...trips.map(([, , t]) => t));
  const d = Array(mx + 1).fill(0);
  for (const [x, f, t] of trips) {
    d[f] += x;
    d[t] -= x;
  }
  let s = 0;
  for (const x of d) {
    s += x;
    if (s > capacity) {
      return false;
    }
  }
  return true;
}

impl Solution {
  pub fn car_pooling(trips: Vec<Vec<i32>>, capacity: i32) -> bool {
    let mx = trips
      .iter()
      .map(|e| e[2])
      .max()
      .unwrap_or(0) as usize;
    let mut d = vec![0; mx + 1];
    for trip in &trips {
      let (x, f, t) = (trip[0], trip[1] as usize, trip[2] as usize);
      d[f] += x;
      d[t] -= x;
    }
    d.iter()
      .scan(0, |acc, &x| {
        *acc += x;
        Some(*acc)
      })
      .all(|s| s <= capacity)
  }
}

/**
 * @param {number[][]} trips
 * @param {number} capacity
 * @return {boolean}
 */
var carPooling = function (trips, capacity) {
  const mx = Math.max(...trips.map(([, , t]) => t));
  const d = Array(mx + 1).fill(0);
  for (const [x, f, t] of trips) {
    d[f] += x;
    d[t] -= x;
  }
  let s = 0;
  for (const x of d) {
    s += x;
    if (s > capacity) {
      return false;
    }
  }
  return true;
};

public class Solution {
  public bool CarPooling(int[][] trips, int capacity) {
    int mx = trips.Max(x => x[2]);
    int[] d = new int[mx + 1];
    foreach (var trip in trips) {
      int x = trip[0], f = trip[1], t = trip[2];
      d[f] += x;
      d[t] -= x;
    }
    int s = 0;
    foreach (var x in d) {
      s += x;
      if (s > capacity) {
        return false;
      }
    }
    return true;
  }
}