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()。
延伸思考
- 如果需要支援「取消出價」操作,資料結構該如何調整?
- 若改為荷蘭式拍賣(價格遞降),設計如何不同?
- 如何確保在高並發環境下的執行緒安全性和出價順序一致性?