解題說明
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):將地圖分成網格,每個網格維護一個司機列表。查詢時先搜尋鄰近網格,再在候選中精確計算距離。適合均勻分佈的場景。
延伸思考
- 如果司機在行程中會移動(位置持續更新),如何高效追蹤?
- 若需要支援「共乘」(一位司機接多位乘客),如何修改分配邏輯?
- 若需要考慮即時交通狀況(動態距離),如何整合路徑規劃?