HardRating 2182
1912. Design Movie Rental System
arrayhash-tabledesignheap-priority-queueordered-set
解題說明
Design Movie Rental System
題目描述：設計一個電影租借系統，包含多家商店，每家商店有不同電影和價格。需支援：search(movie) 回傳擁有該未借出電影的最便宜 5 家商店、rent(shop, movie) 借出、drop(shop, movie) 歸還、report() 回傳當前已借出電影中最便宜的 5 部。
解題思路：用有序集合（set）維護資料。對每部電影維護一個 set<(price, shop)> 存放未借出的副本，方便快速取最便宜的。另外用一個全局 set<(price, shop, movie)> 存放所有已借出的電影。用 map 儲存 (shop, movie) -> price 的映射。rent 時從電影集合移到已借出集合，drop 時反之。
C++ 解法
複雜度分析
時間複雜度：search O(log n)，rent O(log n)，drop O(log n)，report O(log n) — 有序集合的插入/刪除/迭代操作。取前 5 個為常數時間。
空間複雜度：O(E) — E 為所有 entries 的數量，儲存所有電影資訊。
虛擬碼
1. Init: for each entry, add (price, shop) to available[movie] set, store price in map 2. search(movie): iterate first 5 elements of available[movie], return shop IDs 3. rent(shop, movie): remove from available[movie], add to rented set 4. drop(shop, movie): remove from rented set, add back to available[movie] 5. report(): iterate first 5 elements of rented, return [shop, movie] pairs
其他解法
最小堆 + 延遲刪除：用最小堆代替有序集合，rent/drop 時不立即刪除而是標記。search 和 report 時跳過已標記元素。實作更簡單但延遲刪除可能導致堆膨脹。
排序陣列 + 二分搜索：用排序陣列存放可用電影，二分搜索定位插入/刪除位置。插入/刪除 O(n) 但實作簡單，適合操作次數少的場景。
延伸思考
- 若支持修改電影價格，資料結構如何調整？
- 若 search 需要回傳前 K 個結果（K 可變），如何保證效率？
- 若系統需要支持多線程並行操作，如何設計鎖機制？