1094. Car Pooling

Car Pooling

題目描述：一輛車最多載 capacity 名乘客。給定行程陣列 trips，其中 trips[i] = [numPassengers, from, to] 表示在位置 from 上車、to 下車的乘客數。判斷是否能完成所有行程而不超載。

解題思路：使用差分陣列（Difference Array）技巧。由於題目保證站點範圍在 0 到 1000 以內，建立大小為 1001 的差分陣列 diff：對每個行程，在 from 位置加上 numPassengers，在 to 位置減去 numPassengers（乘客到達 to 就下車，所以是開區間右端點）。

接著對差分陣列做前綴和，得到每個位置的實際乘客數。若任一位置的前綴和超過 capacity，回傳 false；否則回傳 true。

此法將所有行程的上下車事件轉換為區間加減，一次線性掃描即可得到每個時間點的車內人數，思路清晰且效率高。

時間複雜度：O(n + M) — 其中 n 為行程數，M = 1001 為站點範圍。處理所有行程需 O(n)，掃描差分陣列需 O(M)，整體為線性。

空間複雜度：O(M) — 差分陣列固定大小為 1001，不隨輸入規模變化，視為 O(1) 也可以接受。

方法一：事件排序（Sweep Line） 將每個行程拆解為兩個事件：(from, +passengers) 和 (to, -passengers)，按位置排序後線性掃描累計人數。同位置需先處理下車事件再處理上車（避免誤超載）。時間複雜度 O(n log n)，空間 O(n)，比差分陣列稍慢但不依賴固定範圍。

方法二：最小堆模擬 將行程按 from 排序，維護一個最小堆記錄正在進行的行程（以 to 為鍵）。每到一個新的 from，先從堆中彈出所有已結束（to <= from）的行程，再加入新行程並計算目前人數。時間複雜度 O(n log n)，空間 O(n)，適合實際調度場景的模擬。

方法三：TreeMap / 有序映射 直接在 map<int,int> 中記錄差分，只儲存有事件的站點，節省稀疏情況下的空間。時間複雜度 O(n log n)，空間 O(n)，適合站點範圍極大但行程數少的情形。

1. 若車輛不止一輛，需要最少幾輛車才能完成所有行程？這與區間排程問題有何關聯？
2. 若站點範圍從 1000 擴大到 10^9，差分陣列的方法是否還適用？應改用哪種資料結構？
3. 若每位乘客有不同的體積（如行李大小），如何修改算法使車輛容量按體積而非人數計算？