題目資訊

題目編號: 2071
題目連結: Maximum Number of Tasks You Can Assign
主題: Array, Binary Search, Greedy, Queue, Sorting, Monotonic Queue

題目敘述

你有 n 個任務和 m 個工人。每個任務有一個存於0起始索引的整數數組 tasks 中的力量需求，第 $i$ 個任務需要 tasks[i] 的力量才能完成。每位工人的力量存於0起始索引的整數數組 workers 中，第 $j$ 個工人有 workers[j] 的力量。每位工人只能被指派到一個任務，且必須擁有大於或等於任務所需的力量（即 $workers[j] \geq tasks[i]$）。

此外，你有 pills 顆魔法藥丸，可以增加一位工人的力量 strength。你可以決定哪些工人獲得魔法藥丸，但每位工人至多只能獲得一顆魔法藥丸。

給定0起始索引的整數數組 tasks 和 workers，以及整數 pills 和 strength，返回最多可以完成的任務數量。

範例 1:

輸入: tasks = [3,2,1], workers = [0,3,3], pills = 1, strength = 1
輸出: 3
解釋:
我們可以如下分配魔法藥丸和任務:
- 給工人 0 魔法藥丸。
- 指派工人 0 到任務 2 (0 + 1 >= 1)
- 指派工人 1 到任務 1 (3 >= 2)
- 指派工人 2 到任務 0 (3 >= 3)

範例 2:

輸入: tasks = [5,4], workers = [0,0,0], pills = 1, strength = 5
輸出: 1
解釋:
我們可以如下分配魔法藥丸和任務:
- 給工人 0 魔法藥丸。
- 指派工人 0 到任務 0 (0 + 5 >= 5)

範例 3:

輸入: tasks = [10,15,30], workers = [0,10,10,10,10], pills = 3, strength = 10
輸出: 2
解釋:
我們可以如下分配魔法藥丸和任務:
- 給工人 0 和工人 1 魔法藥丸。
- 指派工人 0 到任務 0 (0 + 10 >= 10)
- 指派工人 1 到任務 1 (10 + 10 >= 15)
最後一顆藥丸沒有給出，因為它不會讓任何工人足夠強大以完成最後的任務。

約束條件:

$n == tasks.length$
$m == workers.length$
$1 \leq n, m \leq 5 \times 10^4$
$0 \leq pills \leq m$
$0 \leq tasks[i], workers[j], strength \leq 10^9$

直覺

這個問題涉及將任務分配給工人，要求工人的力量至少滿足或超過所分配任務的要求。此外，我們可以使用魔法藥丸暫時增加工人的力量，使他們能完成任務。核心挑戰是在這些限制下最大化能夠完成的任務數量。

一個關鍵的洞察是結合使用貪心策略和二分搜尋：從不使用藥丸的最簡單情況開始，然後僅在必要時逐步引入藥丸。我們將 tasks 和 workers 陣列排序，以有序管理哪個工人承擔哪個任務。通過對任務數量進行二分搜尋，我們可以有效地找到可以分配的最大任務數量。

解法

排序： 首先對 tasks 和 workers 陣列進行排序。這有助於根據力量輕鬆匹配任務和工人，並確保資源的有效分配。
二分搜尋設定： 我們想要確定在給定工人力量和可用藥丸的情況下可以完成的最大任務數量。設置二分搜尋的範圍，left = 0 和 right = min(n, m)，其中 $n$ 是任務數量，$m$ 是工人數量。目標是找到可以完成任務的最大 mid 值（任務數量）。
檢查可行性（canDo輔助函數）：
- 對於二分搜尋中的每個中間點 mid，檢查是否可以完成 mid 個任務。
- 使用多重集合來跟蹤當前檢查中可用的 k 個最強工人，其中 $k = \text{mid}$。
- 嘗試將每個任務分配給可以不用或用藥丸完成它的最強可用工人。這涉及：
  - 使用 availableWorkers.lower_bound(taskStrength) 檢查工人是否能不使用藥丸完成任務。
  - 如果不可能，用 availableWorkers.lower_bound(taskStrength - strength) 嘗試將任務分配給需要藥丸才能完成任務的工人。如果採用了這條路徑，則減少可用的藥丸數量。
執行二分搜尋：
- 如果當前 mid 數量的任務可以完成，我們將搜尋範圍右移 (left = mid + 1) 以查看是否可以處理更多任務。
- 如果不能，則將搜尋範圍左移 (right = mid - 1)。
結果： 二分搜尋結束後，maxTasks 將保存通過最優地分配工人和藥丸可以完成的最大任務數量。返回此值。

通過這種方式結構化解決方案，我們實現了一種使用排序和二分搜尋的時間效率高的方法，有效管理力量需求和資源分配。這種方法確保我們在所提供的限制內探索最大配置。

程式碼

C++

class Solution {
public:
    // 輔助函式，用於判斷是否可以完成 `k` 個任務。
    bool canDo(int k, const vector<int>& tasks, const vector<int>& workers, int pills, int strength) {
        if (k > tasks.size() || k > workers.size()) return false;

        // 考慮最強的 k 個工人
        multiset<int> availableWorkers(workers.end() - k, workers.end());
        int pillsLeft = pills;

        // 遍歷需要分配的任務
        for (int i = k - 1; i >= 0; --i) {
            int taskStrength = tasks[i];
            auto it = availableWorkers.lower_bound(taskStrength);
            
            if (it != availableWorkers.end()) {
                availableWorkers.erase(it);
            } else {
                if (pillsLeft == 0) return false;

                // 找到一個可以使用藥丸來完成任務的工人
                it = availableWorkers.lower_bound(taskStrength - strength);
                if (it == availableWorkers.end()) return false;
                
                availableWorkers.erase(it);
                --pillsLeft;
            }
        }
        return true;
    }

    // 找出可以分配的最大任務數量的函式
    int maxTaskAssign(vector<int>& tasks, vector<int>& workers, int pills, int strength) {
        sort(tasks.begin(), tasks.end());
        sort(workers.begin(), workers.end());

        int taskCount = tasks.size();
        int workerCount = workers.size();
        int left = 0, right = min(taskCount, workerCount), maxTasks = 0;

        // 使用二分搜尋找到最佳的任務數量
        while (left <= right) {
            int mid = (left + right) / 2;
            if (canDo(mid, tasks, workers, pills, strength)) {
                maxTasks = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return maxTasks;
    }
};

Python

from typing import List
from collections import Counter

class Solution:
    # 輔助函數來判斷是否能完成 `k` 個工作。
    def canDo(self, k: int, tasks: List[int], workers: List[int], pills: int, strength: int) -> bool:
        if k > len(tasks) or k > len(workers):
            return False

        # 考慮力量最強的 k 個工人
        availableWorkers = Counter(workers[-k:])
        pillsLeft = pills

        # 迭代需要分配的任務
        for i in range(k - 1, -1, -1):
            taskStrength = tasks[i]

            it = next((w for w in availableWorkers if w >= taskStrength), None)
            if it is not None:
                availableWorkers[it] -= 1
                if availableWorkers[it] == 0:
                    del availableWorkers[it]
            else:
                if pillsLeft == 0:
                    return False

                # 找到一個可以在加強藥丸的力量下完成任務的工人
                it = next((w for w in availableWorkers if w >= taskStrength - strength), None)
                if it is None:
                    return False

                availableWorkers[it] -= 1
                if availableWorkers[it] == 0:
                    del availableWorkers[it]
                pillsLeft -= 1

        return True

    # 函數用於查找可以分配的最大任務數量
    def maxTaskAssign(self, tasks: List[int], workers: List[int], pills: int, strength: int) -> int:
        tasks.sort()
        workers.sort()

        taskCount = len(tasks)
        workerCount = len(workers)
        left, right, maxTasks = 0, min(taskCount, workerCount), 0

        # 二分搜尋以找到最佳的任務數量
        while left <= right:
            mid = (left + right) // 2
            if self.canDo(mid, tasks, workers, pills, strength):
                maxTasks = mid
                left = mid + 1
            else:
                right = mid - 1

        return maxTasks

複雜度分析

時間複雜度: $O(n \log n + m \log m + n \log \min(n, m))$
時間複雜度是由演算法的幾個部分推導出來的：
1. 排序 tasks 和 workers 陣列分別需時 $O(n \log n)$ 和 $O(m \log m)$。
2. 對任務數量的二分搜尋形成一個複雜度為 $O(\log \min(n, m))$ 的循環。
3. 在二分搜尋的每次迭代中調用的 canDo 函數，最壞情況下由於多重集的操作以及迭代最多 $n$ 個任務，需要 $O(n \log n)$ 的時間。
綜合這些，整體的時間複雜度為 $O(n \log n + m \log m + n \log \min(n, m))$。
空間複雜度: $O(n)$
空間複雜度主要由 canDo 函數中使用的多重集決定，它在最壞情況下會儲存最多 $n$ 個工人。因此，空間複雜度為 $O(n)$。使用的其他變數和迭代器需要的空間是常數空間，不會影響整體的空間複雜度。

CS Note
En

Leetcode 2071. Maximum Number of Tasks You Can Assign

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析