解題說明
Design Ride Sharing System
題目描述：設計一個共乘系統，支援以下操作：(1) addDriver(driverId, location) — 新增一個可用司機及其位置；(2) requestRide(rideId, pickupLocation) — 乘客請求乘車，分配最近的可用司機；(3) completeRide(rideId) — 完成行程，司機重新變為可用。回傳被分配的司機 ID，若無可用司機回傳 -1。若距離相同，選擇 ID 最小的司機。
解題思路：使用雜湊表管理司機狀態。可用司機放在一個集合中，每個司機的位置另外儲存。收到叫車請求時，遍歷所有可用司機，計算與乘客位置的距離（曼哈頓距離或歐幾里得距離），選最近的。分配後將司機標記為忙碌。完成行程後將司機重新標記為可用。
若需要更高效的空間查詢，可以用 KD-Tree 或空間索引，但在司機數量不大時，線性掃描即可。
C++ 解法
複雜度分析
時間複雜度：addDriver O(1)；requestRide O(D) — D 為可用司機數，需遍歷所有可用司機計算距離；completeRide O(1)。
空間複雜度：O(D + R) — D 為司機總數，R 為進行中的行程數。
虛擬碼
1. Maintain: driverLocation map, available set, rideToDriver map 2. addDriver(id, loc): store location, add to available set 3. requestRide(rideId, pickup): a. If no available drivers: return -1 b. Find driver with min distance to pickup (break ties by smallest ID) c. Remove from available, map rideId -> driverId d. Return driverId 4. completeRide(rideId): a. Look up driver from rideToDriver b. Add driver back to available set c. Remove ride mapping
其他解法
KD-Tree O(log D)：將可用司機的座標存入 KD-Tree，支援最近鄰查詢 O(log D)。插入和刪除也是 O(log D)。適合司機數量很大的場景。
網格索引（Grid-based Spatial Index）：將地圖分成網格，每個網格維護一個司機列表。查詢時先搜尋鄰近網格，再在候選中精確計算距離。適合均勻分佈的場景。
延伸思考
- 如果司機在行程中會移動（位置持續更新），如何高效追蹤？
- 若需要支援「共乘」（一位司機接多位乘客），如何修改分配邏輯？
- 若需要考慮即時交通狀況（動態距離），如何整合路徑規劃？