MediumRating 1807
3408. Design Task Manager
hash-tabledesignheap-priority-queueordered-set
解題說明
Design Task Manager
題目描述：設計一個任務管理器，支援以下操作：(1) add(userId, taskId, priority) — 新增任務；(2) edit(taskId, newPriority) — 修改任務優先級；(3) rmv(taskId) — 移除任務；(4) execTop() — 執行並移除優先級最高的任務（若相同優先級則選 taskId 最大的），回傳該任務的 userId。
解題思路：使用一個有序集合（如 C++ 的 set）儲存 (priority, taskId) 對，支援 O(log n) 的插入、刪除和最大值查詢。另用雜湊表 taskId -> (userId, priority) 記錄每個任務的詳細資訊。edit 操作先刪除舊條目再插入新條目。execTop 取有序集合中最大元素。
C++ 解法
複雜度分析
時間複雜度：每個操作 O(log n) — set 的插入、刪除和查詢最值均為 O(log n)。
空間複雜度：O(n) — 儲存所有任務的 set 和 hash map。
虛擬碼
1. Maintain ordered set of (priority, taskId) pairs 2. Maintain hash map: taskId -> (userId, priority) 3. add: insert into both structures 4. edit: remove old (priority, taskId) from set, update priority, re-insert 5. rmv: remove from both structures 6. execTop: get max from set (last element), remove and return userId
其他解法
最大堆 + 懶刪除 O(log n) 均攤：使用 priority_queue 存 (priority, taskId)，edit 和 rmv 時不立即刪除，而是標記為已刪除。execTop 時跳過已刪除的條目。均攤效率好但最壞情況下 execTop 可能需要 pop 多個無效元素。
平衡 BST（如 std::map）O(log n)：與 set 方案本質相同。若需要更多功能（如第 k 大），可考慮 Order Statistics Tree。
延伸思考
- 如果要支援
execKth(k)— 執行第 k 高優先級的任務，如何擴展資料結構？ - 如果多個用戶同時操作（並發環境），如何確保資料結構的線程安全？
- 如果需要支援按 userId 查詢所有任務，需要額外維護什麼資料結構？