MediumRating 1854
3815. Design Auction System
hash-tabledesignheap-priority-queueordered-set
解題說明
Design Auction System
題目描述：設計一個拍賣系統，支援以下操作：(1) createAuction(auctionId, startTime, endTime) — 建立一個新拍賣；(2) placeBid(auctionId, userId, amount, timestamp) — 在指定拍賣中出價；(3) closeAuction(auctionId, timestamp) — 結束拍賣並回傳得標者資訊。出價必須在拍賣有效期間內且高於當前最高出價。結束時回傳最高出價者（若同額則最早出價者優先）。
解題思路：使用雜湊表存儲每個拍賣的資訊。每個拍賣維護：開始/結束時間、當前最高出價和出價者。出價時檢查：(1) 拍賣存在且在有效時間內；(2) 出價金額高於當前最高出價。結束拍賣時回傳最高出價者。由於只需要追蹤最高出價，不需要堆或有序集合 — 簡單比較即可。但若需要支援取消出價等功能，則需要更複雜的資料結構。
C++ 解法
複雜度分析
時間複雜度：createAuction O(1)；placeBid O(1)；closeAuction O(1) — 所有操作均為常數時間。
空間複雜度：O(A) — A 為拍賣數量。
虛擬碼
1. Maintain hash map: auctionId -> {startTime, endTime, highestBid, winnerId, closed}
2. createAuction(id, start, end): store new auction
3. placeBid(id, userId, amount, time):
a. Validate: auction exists, not closed, time in [start, end]
b. If amount > highestBid: update highestBid, winnerId
c. Return success/failure
4. closeAuction(id, time):
a. Mark auction as closed
b. Return [winnerId, highestBid] or [] if no bids其他解法
最大堆維護所有出價：用 max-heap 存儲所有出價 (amount, -timestamp, userId)。closeAuction 時取堆頂。支援更多功能（如查詢前 k 名出價），但記憶體開銷更大。
有序集合 (std::set)：用 set<tuple<int,int,int>> 按 (amount, timestamp, userId) 排序。支援任意排名查詢和出價撤銷。closeAuction 取 rbegin()。
延伸思考
- 如果需要支援「取消出價」操作，資料結構該如何調整？
- 若改為荷蘭式拍賣（價格遞降），設計如何不同？
- 如何確保在高並發環境下的執行緒安全性和出價順序一致性？