1094.拼车
车上最初有 capacity 个空座位。车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向）
给定整数 capacity 和一个数组 trips , trips[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

• 定义数组dif, dif[i]表示行驶到i公里时乘客的变动情况
• 比如例1中trips[0]为[2,1,5]，表示行驶到1公里时乘客+2，行驶到5公里时乘客-2，对应的dif[1]+=2,dif[5]-=2
• 遍历完 trips 我们就得到了在行驶到每个i公里时乘客的变动情况
• 最后遍历dif，从0累加每个元素就能知道行驶到i公里时此时有几个乘客
• 其实上述解法就暗合了差分数组的理念，对应到本题当中，设a[i]为行驶到i时车上乘客数，我们的dif就是数组a所对应的差分数组，每个trip是a[form]~a[to-1]增加了numPassengers个乘客，所以我们每次只改变 dif[from] 和 dif[to]

•   public boolean carPooling(int[][] trips, int capacity) {int[] dif = new int[1001];for(int[] t:trips){dif[t[1]]+=t[0];dif[t[2]]-=t[0];}int sum = 0;for(int d:dif){sum+=d;if(sum>capacity)return false;}return true;}
  

• 由于我们只需要考虑乘客数变动时的每个行程节点，所以也可以用map存储每个节点的变化（用数组有很多元素可能用不上），遍历时按照节点公里数从小到大的顺序，整体逻辑没变

•   var carPooling = function(trips, capacity) {const dif = {};for(let t of trips){const [n, from, to] = t;dif[from] = (dif[from] || 0) + n;dif[to] = (dif[to] || 0) - n;}let sum = 0;for(let i of Object.keys(dif).sort((a,b)=>a-b)){sum += dif[i];if(sum > capacity)return false;}return true;};