MediumRating 1851

3508. Implement Router

arrayhash-tablebinary-searchdesignqueueordered-set

解題說明

Implement Router

題目描述：設計一個路由器系統，支援以下操作：(1) addPacket(source, destination, timestamp) — 將封包加入路由器佇列，若該封包（相同 source、destination、timestamp）已存在則拒絕並回傳 false；(2) forwardPacket() — 轉發佇列中最早的封包並回傳其資訊，若佇列為空回傳空陣列；(3) getCount(destination, startTime, endTime) — 查詢在 [startTime, endTime] 時間範圍內送往指定目的地的封包數量。

解題思路：需要同時支援去重、FIFO 轉發、以及按目的地和時間範圍查詢。使用雜湊集合 (set) 儲存三元組 (source, dest, timestamp) 做去重檢查。使用佇列 (queue) 維護 FIFO 順序。對於按目的地查詢，維護一個 map<int, vector<int>>，將每個目的地的 timestamp 按順序存入有序陣列，查詢時用二分搜尋找到 [startTime, endTime] 範圍內的數量。

C++ 解法

複雜度分析

時間複雜度：addPacket O(log n) — 集合插入；forwardPacket O(log n) — 集合刪除；getCount O(log m) — 二分搜尋，m 為該目的地的封包數。

空間複雜度：O(n) — 儲存所有封包的佇列、集合、與目的地時間戳。

虛擬碼

1. Maintain: queue Q for FIFO, set S for dedup, map D[dest] -> sorted timestamps
2. addPacket(src, dest, ts):
   a. If (src, dest, ts) in S: return false
   b. Add to S, push to Q, append ts to D[dest]
   c. Return true
3. forwardPacket():
   a. If Q empty: return []
   b. Pop front (src, dest, ts), remove from S, return [src, dest, ts]
4. getCount(dest, start, end):
   a. Binary search D[dest] for lower_bound(start) and upper_bound(end)
   b. Return count = upper - lower

其他解法

有序集合 (std::multiset)：用 multiset<pair<int,int>> 存 (timestamp, dest)，支援範圍查詢，但按 dest 過濾需額外遍歷，效率較差。

分桶法：按目的地分桶，每個桶內用有序結構存封包，查詢時直接定位目的地桶再二分搜尋。本質上與主解法相同。

延伸思考

如果路由器有記憶體上限，滿了之後需要丟棄最舊的封包，如何修改 addPacket？
如果需要支援「撤銷最近一次 forwardPacket」操作，該如何設計？
在多執行緒環境下，如何確保這些操作的執行緒安全性？

Implement Router — CaffeCode