5、拼车

/**
 * @param {number[][]} trips
 * @param {number} capacity
 * @return {boolean}
 */
var carPooling = function (trips, capacity) {
  // 实现一个差分数组
  class Difference {
    constructor(nums) {
      // 原始数组
      this.nums = nums;
      this.initDef();
    }
    initDef() {
      // 差分数组初始化
      this.diffs = [this.nums[0]];
      // 完整获取差分数组
      for (let i = 1; i < this.nums.length; i++) {
        this.diffs[i] = this.nums[i] - this.nums[i - 1];
      }
    }
    /** 区间增加 */
    increment(s, e, val) {
      // 头部 +1
      this.diffs[s] += val;
      // 如果不是最后一个，则设置差分的结束地址
      if (e < this.nums.length) {
        this.diffs[e + 1] -= val;
      }
    }
    result() {
      const list = [this.diffs[0]];
      for (let i = 1; i < this.diffs.length; i++) {
        list[i] = this.diffs[i] + list[i - 1];
      }
      return list;
    }
  }

  // 初始化一个长度为 1001 的数组 因为题目给出的范围是 0 <= trips[i][1] < trips[i][2] <= 1000
  const nums = new Array(1001).fill(0);
  // 构造差分数组
  const diff = new Difference(nums);
  // 对差分数组进行增加
  for (let i = 0; i < trips.length; i++) {
    const [num, start, end] = trips[i];
    // end 站乘客下车，不占据容量
    diff.increment(start, end - 1, num);
  }
  const list = diff.result();
  // 如果有一个地方超过了 capacity 证明次站点超过了容量，返回 false
  return Math.max(...list) <= capacity;
};