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;};