HardRating 2648

2071. Maximum Number of Tasks You Can Assign

arraytwo-pointersbinary-searchgreedyqueuesortingmonotonic-queue

在 LeetCode 上作答 ↗

解題說明

Maximum Number of Tasks You Can Assign

題目描述：有 m 個任務和 n 個工人，每個任務有難度 tasks[i]，每個工人有能力 workers[j]。有 pills 顆藥丸，每顆可讓一個工人的能力增加 strength。每個工人最多吃一顆藥。求最多能完成多少個任務。

解題思路：二分搜尋答案 + 貪心驗證。

二分搜尋：答案具有單調性——若能完成 k 個任務，則必然能完成 k-1 個。二分搜尋最大的 k。
貪心驗證（能否完成 k 個任務）：
- 選最簡單的 k 個任務和最強的 k 個工人。
- 將任務從難到易考慮。對每個任務：
  - 若最強的工人（不吃藥）能完成，直接分配。
  - 否則，找能力最弱但吃藥後能完成的工人來做（貪心：藥丸盡量給弱工人用）。
  - 若都不行，則 k 不可行。
- 使用有序多重集（multiset）管理可用工人，高效查找和移除。

最弱的能吃藥完成的工人 = multiset 中 lower_bound(task - strength) 的最小值。

C++ 解法

複雜度分析

時間複雜度：O((m + n) log(min(m, n)) * log(min(m, n))) — 二分搜尋 O(log(min(m,n))) 層，每層驗證時建立 multiset O(k log k) 並做 k 次查找/刪除 O(log k)。排序 O(m log m + n log n)。

空間複雜度：O(min(m, n)) — multiset 最多存 k 個工人。

虛擬碼

1. Sort tasks ascending, sort workers ascending.
2. Binary search on k (number of tasks to complete):
   a. CAN_ASSIGN(k):
      - Put the k strongest workers into a multiset.
      - pillsLeft = pills.
      - For i = k-1 down to 0 (hardest to easiest of the k tasks):
        - If strongest available worker >= tasks[i]: assign, remove from set.
        - Else if pillsLeft > 0:
          - Find weakest worker >= tasks[i] - strength in set.
          - If found: assign, remove, pillsLeft--.
          - Else: return false.
        - Else: return false.
      - Return true.
   b. If CAN_ASSIGN(mid): try larger. Else: try smaller.
3. Return max feasible k.

其他解法

反向貪心策略：將任務從易到難分配，對每個任務先嘗試最弱的能完成的工人，不行再考慮吃藥。這樣藥丸會分配給需要做較難任務的工人。但這種策略不一定最優，因為可能浪費強工人在簡單任務上。
最大匹配（二分圖匹配）：將問題建模為二分圖，任務和工人為兩側，若工人能完成任務則連邊。求最大匹配。但需要枚舉哪些工人吃藥（2^n 種），不實際。

延伸思考

若每顆藥丸的增強值不同（有多種藥丸），如何修改貪心策略？
若工人可以吃多顆藥丸（但有上限 K 顆），問題的複雜度會如何變化？
若任務有截止時間且工人完成每個任務需要不同時間，問題如何轉化為排程問題？

解題說明

Maximum Number of Tasks You Can Assign

解題思路：二分搜尋答案 + 貪心驗證。

二分搜尋：答案具有單調性——若能完成 k 個任務，則必然能完成 k-1 個。二分搜尋最大的 k。
貪心驗證（能否完成 k 個任務）：
- 選最簡單的 k 個任務和最強的 k 個工人。
- 將任務從難到易考慮。對每個任務：
  - 若最強的工人（不吃藥）能完成，直接分配。
  - 否則，找能力最弱但吃藥後能完成的工人來做（貪心：藥丸盡量給弱工人用）。
  - 若都不行，則 k 不可行。
- 使用有序多重集（multiset）管理可用工人，高效查找和移除。

最弱的能吃藥完成的工人 = multiset 中 lower_bound(task - strength) 的最小值。

虛擬碼

1. Sort tasks ascending, sort workers ascending. 2. Binary search on k (number of tasks to complete): a. CAN_ASSIGN(k): - Put the k strongest workers into a multiset. - pillsLeft = pills. - For i = k-1 down to 0 (hardest to easiest of the k tasks): - If strongest available worker >= tasks[i]: assign, remove from set. - Else if pillsLeft > 0: - Find weakest worker >= tasks[i] - strength in set. - If found: assign, remove, pillsLeft--. - Else: return false. - Else: return false. - Return true. b. If CAN_ASSIGN(mid): try larger. Else: try smaller. 3. Return max feasible k.

其他解法

反向貪心策略：將任務從易到難分配，對每個任務先嘗試最弱的能完成的工人，不行再考慮吃藥。這樣藥丸會分配給需要做較難任務的工人。但這種策略不一定最優，因為可能浪費強工人在簡單任務上。
最大匹配（二分圖匹配）：將問題建模為二分圖，任務和工人為兩側，若工人能完成任務則連邊。求最大匹配。但需要枚舉哪些工人吃藥（2^n 種），不實際。