解題說明
Design Underground System
題目描述： 設計一個地鐵系統，支援三種操作：
checkIn(id, stationName, t)— 乘客 id 在時間 t 從 stationName 進站。checkOut(id, stationName, t)— 乘客 id 在時間 t 從 stationName 出站。getAverageTime(startStation, endStation)— 回傳從 startStation 到 endStation 的平均旅行時間。
解題思路： 使用兩個雜湊表：
checkInMap：記錄每個乘客的進站資訊{id -> (station, time)}。checkIn 時寫入，checkOut 時讀取並刪除。travelMap：記錄每對站點之間的旅行統計{(start, end) -> (totalTime, count)}。checkOut 時計算本次旅行時間並累加。
getAverageTime 直接查 travelMap 計算 totalTime / count。
C++ 解法
複雜度分析
時間複雜度：checkIn O(1)、checkOut O(1)、getAverageTime O(1) — 所有操作都是雜湊表的常數時間查詢。
空間複雜度：O(P + S^2) — P 為同時在站內的乘客數，S^2 為所有站點對的數量。
虛擬碼
1. Maintain two maps: - checkInMap: id -> (startStation, startTime) - travelMap: (start, end) -> (totalTime, count) 2. checkIn(id, station, t): store (station, t) in checkInMap[id] 3. checkOut(id, station, t): a. Retrieve (startStation, startTime) from checkInMap[id] b. route = (startStation, station) c. travelMap[route].totalTime += (t - startTime) d. travelMap[route].count += 1 e. Remove id from checkInMap 4. getAverageTime(start, end): return travelMap[(start,end)].totalTime / travelMap[(start,end)].count
其他解法
儲存所有旅程記錄：不做累計，而是在 travelMap 中存所有旅行時間的列表。getAverageTime 時遍歷列表計算平均值。空間 O(所有旅程數)，getAverageTime 時間 O(旅程數)，效率較差但可支援更多統計查詢（如中位數、標準差）。
使用複合鍵：用 pair<string, string> 作為 map 鍵，搭配自定義雜湊函式，避免字串拼接。效能略好但實作稍繁瑣。
延伸思考
- 如何擴展系統以支援查詢某段時間範圍內的平均旅行時間？
- 若乘客可能同時搭乘多條路線（轉乘），如何修改設計？
- 若要支援查詢「最快」和「最慢」的旅行時間，需要儲存什麼額外資訊？