2071. 你可以安排的最多任務數目

思路

給你 $n$ 個任務和 $m$ 個工人。每個任務需要一定的力量值才能完成，需要的力量值保存在下標從 $0$ 開始的整數陣列 tasks 中，第 $i$ 個任務需要 tasks[i] 的力量才能完成。

每個工人的力量值保存在下標從 $0$ 開始的整數陣列 workers 中，第 $j$ 個工人的力量值為 workers[j]。每個工人只能完成 一個 任務，且力量值必須 $\geq$ 該任務的力量要求值（即 workers[j] >= tasks[i]）。

除此之外，你還有 pills 個神奇藥丸，可以給 一個工人 的力量值增加 strength。你可以決定給哪些工人使用藥丸，但每個工人 最多只能使用一片 藥丸。

給你下標從 0 開始的整數陣列 tasks 和 workers 以及兩個整數 pills 和 strength，請你返回 最多 有多少個任務可以被完成。

1. 直接判斷有多少任務可以被完成很困難
2. 判斷能否完成 $x$ 個任務比較簡單。
3. 任務數量越多，任務就越難完成。

根據前面幾點，能用二分查找去找出最多有多少任務能被完成。

• 最差情況只能完成 0 個任務。
• 最好情況可以完成所有任務，或是所有工人都有完成任務： $\min(n,m)$ 。

接下來，要判斷 $m$ 個工人能否完成 $n$ 個任務。

• 錯誤想法：如果工人 $j$ 不吃藥過不了任務 $i$ ，就直接讓他吃藥。
  • 如果工人 $j$ 吃藥可以過任務 $i$ ，會不會有另一個更弱的工人 $k$ ，吃藥也能過任務 $i$ ？這時應該要讓更弱的工人吃藥，把比較強的工人留給更難的任務，因為 $j$ 可能不吃藥，也能完成後面的某個任務。

現在只要求完成 $n$ 個任務，那麼肯定是選擇力量要求最低的前 $n$ 個任務，以及最強的 $n$ 個工人試著去完成這些任務。
接下來要看看哪些工人要吃藥丸，且吃的數量不能超過pills顆，以下舉例。
任務： $[3,3,10,12,14,15,20,22]$
工人： $[3,5,5,10,12,12,15,18]$
吃藥可以加 $8$ 力量。

1. 第一個工人 3
   • 把自己不吃藥，能夠完成的任務解鎖，加入到隊列當中： $queue = [3,3]$
   • 看看隊列裡面有沒有任務，是自己可以完成的，發現有，做第一個，3。
2. 第二個工人 5
   • 把自己不吃藥，能夠完成的任務解鎖，加入到隊列當中，發現沒有： $queue = [3]$
   • 看看隊列裡面有沒有任務，是自己可以完成的，發現有，做第一個，3。
3. 第三個工人 5
   • 把自己不吃藥，能夠完成的任務解鎖，加入到隊列當中，發現沒有：： $queue = []$
   • 看看隊列裡面有沒有任務，是自己可以完成的，沒有。
   • 這個工人沒有任務可做，但每個工人都必須要工作，得吃藥增加力量。
   • 把自己吃藥，能夠完成的任務解鎖，加入到隊列當中： $queue=[10,12,14,15]$
   • 自己已經吃了藥，後面的工人不一定有機會吃藥，擔當重任，做解鎖任務中最難的，15。
4. 第四個工人 10
   • 把自己不吃藥，能夠完成的任務解鎖，加入到隊列當中，發現沒有： $queue = [10,12,14]$
   • 看看隊列裡面有沒有任務，是自己可以完成的，發現有，做第一個，10。
5. 第五個工人 12
   • 把自己不吃藥，能夠完成的任務解鎖，加入到隊列當中，發現沒有： $queue = [12,14]$
   • 看看隊列裡面有沒有任務，是自己可以完成的，發現有，做第一個，12。
6. 第六個工人 12
   • 把自己不吃藥，能夠完成的任務解鎖，加入到隊列當中，發現沒有： $queue = [14]$
   • 看看隊列裡面有沒有任務，是自己可以完成的，沒有。
   • 這個工人沒有任務可做，但每個工人都必須要工作，得吃藥增加力量。
   • 把自己吃藥，能夠完成的任務解鎖，加入到隊列當中： $queue=[14,20,22]$ 。
   • 自己已經吃了藥，後面的工人不一定有機會吃藥，擔當重任，做解鎖任務中最難的，22。
7. 第七個工人 15
   • 把自己不吃藥，能夠完成的任務解鎖，加入到隊列當中，發現沒有： $queue = [14,15,20]$
   • 看看隊列裡面有沒有任務，是自己可以完成的，發現有，做第一個，14。
8. 第八個工人 18
   • 把自己不吃藥，能夠完成的任務解鎖，加入到隊列當中，發現沒有： $queue = [20]$
   • 看看隊列裡面有沒有任務，是自己可以完成的，沒有。
   • 這個工人沒有任務可做，但每個工人都必須要工作，得吃藥增加力量。
   • 把自己吃藥，能夠完成的任務解鎖，加入到隊列當中，保持相同模樣： $queue=[20]$ 。
   • 自己已經吃了藥，後面的工人不一定有機會吃藥，擔當重任，做任務中最難的，20。

• 任務跟工人的數量相同，所以每個工人都一定要做一個任務。
• 對於沒吃藥的工人來說，後面的工人力氣都比自己大，在「解鎖」的任務當中，自己應該挑最輕鬆的做，避免後面工人的力氣浪費在簡單任務上。
• 對於吃藥的工人來說，後面的工人力氣不一定比自己大，在「解鎖」的任務當中，自己應該挑最難的做，讓自己吃的藥能發揮最大效用。

一言以蔽之：田忌賽馬

程式碼

1. 二分查找 + 單調隊列

class Solution {
private:
    static const int MX = 1e5 + 1;
    int dq[MX]; // 紀錄當前工作對應的下標
public:
    int maxTaskAssign(vector<int>& tasks, vector<int>& workers, int pills, int strength) {
        int n = tasks.size();
        int m = workers.size();
    
        auto canComplete = [&](int need) -> bool { // 判斷能不能完成 need 個任務
            int usedPills = 0;
            int left = 0, right = 0;
            // i 指向當前還沒解鎖的工作, j 指向現在的工人
            for(int i = 0, j = m - need; j < m; j++) {
                // 先解鎖當前工人的力量所能完成的工作
                while(i < need && tasks[i] <= workers[j]) {
                    dq[right++] = i++;
                }
                // 如果當前解鎖的工作中，有自己可以完成的工作，就去做它
                if(left != right && tasks[dq[left]] <= workers[j]) {
                    left++;
                }
                else { // 沒有工作可做，工人著急，於是嗑藥，解鎖更多工作
                    if(++usedPills > pills) return false; // 不可以嗑那麼多藥
                    while(i < need && tasks[i] <= workers[j] + strength) {
                        dq[right++] = i++;
                    }
                    // 嗑藥解鎖工作之後，擔當重責大任，做最難的工作。
                    if(left != right && tasks[dq[right - 1]] <= workers[j] + strength) {
                        right--;
                    }
                    else { // 縱使嗑藥，依舊沒工作，我很遺憾，請你另尋出路。
                        return false;
                    }
                }
            }
            return true;
        };

        ranges::sort(tasks); // 將 tasks 所需的力量值由小到大排列
        ranges::sort(workers); // 將工人的力量從小到大排列
        int left = 0, right = min(n, m); // 閉區間，最差能完成 0 個任務, 最佳能完成 min(任務數量, 工人一人完成一個任務)
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(canComplete(mid)) { 
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        // int left = 0, right = min(n, m) + 1; // 開區間
        // while(left + 1 < right) {
        //     int mid = left + (right - left) / 2;
        //     (canComplete(mid) ? left : right) = mid;
        // }
        return right;
    }
};

複雜度分析

• 時間複雜度：$O(n\log{n})$
• 空間複雜度：$O(n)$