🔗 🟡 826. Most Profit Assigning Work 1709

tags: `Weekly Contest 82` `貪心(Greedy)` `排序(Sorting)` `雙指標(Two Pointers)` `二分搜尋(Binary Search)`

題意

給定兩個長度為 $n$ 的陣列 $\textit{difficulty}$ 和 $\textit{profit}$ ，以及一個長度為 $m$ 的陣列 $\textit{worker}$ ，其中：

$\textit{difficulty}[i]$ 表示第 $i$ 個工作的難度， $\textit{profit}[i]$ 表示第 $i$ 個工作的收益。
$\textit{worker}[i]$ 是第 $i$ 個工人的能力，即該工人只能完成難度 $\leq \textit{worker}[i]$ 的工作。

每個工人最多可以完成一個工作，但一個工作可以被不同的工人 完成多次 。

返回將工作分配給工人後，可以獲得的最大利潤。

思路：排序(Sorting) + 雙指標(Two Pointers) / 二分搜尋(Binary Search)

首先確定主要思路：對於每個工人，要在其可以完成的工作中選擇利潤最大的工作。

方法一：排序(Sorting) + 雙指標(Two Pointers)

為找到可以每個工人完成的工作，可以將工作按照難度排序，且也對工人按照能力排序。從能力最小的工人開始，對於每個工人，找到其能完成的最大利潤的工作。

由於前面工人完成的任務，後面的工人也可以完成，因此可以使用雙指標(Two Pointers) 的方式來找到每個工人可以完成的工作。 $i$ 指向當前可以完成的難度最大的工作、 $j$ 指向當前枚舉的工人、 $mx$ 紀錄當前工人可以完成的最大利潤，範例中直接使用 $w$ 來枚舉工人。

在遍歷每個工人時，將 $i$ 移動到最後一個可以完成的工作，並在每次移動時將 $mx$ 更新為當前工人可以完成的最大利潤，最後將 $mx$ 加到答案中。

複雜度分析

時間複雜度： $O(n \log n + m \log m)$ ，主要為排序的時間複雜度，雙指標分別最多移動 $n$ 和 $m$ 次。
空間複雜度： $O(n)$ ，用於存儲排序後的工作。

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        n, m = len(difficulty), len(worker)
        tasks = sorted(zip(difficulty, profit))
        worker.sort()
        ans, i, mx = 0, 0, 0
        # for j, w in enumerate(worker):
        for w in worker:
            while i < n and tasks[i][0] <= w: # find the last task that can be done
                mx = max(mx, tasks[i][1]) # max profit
                i += 1
            ans += mx
        return ans

class Solution {
public:
    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
        int n = difficulty.size(), m = worker.size();
        vector<pair<int, int>> tasks;
        for (int i = 0; i < n; i++) tasks.push_back({difficulty[i], profit[i]});
        sort(tasks.begin(), tasks.end());
        sort(worker.begin(), worker.end());
        int ans = 0, i = 0, mx = 0;
        for (int w : worker) {
            while (i < n && tasks[i].first <= w) { // find the last task that can be done
                mx = max(mx, tasks[i].second); // max profit
                i++;
            }
            ans += mx;
        }
        return ans;
    }
};

方法二：排序(Sorting) + 二分搜尋(Binary Search)

在將任務依照難度排序後，我們可以注意到，對於每個工人的能力 $w$ ，要找到最後一個可以完成的工作，即找到最大的 $idx$ 使得 $tasks[idx][0] \leq w$ ，這個過程可以使用二分搜尋(Binary Search) 來實現，也就是使用 bisect_right 或 upper_bound 來找到第一個 $> w$ 的位置，再 $-1$ 即可。若結果 $idx < 0$ ，則表示沒有任務可以完成。

但到這裡會有另外一個問題，我們需要在每次二分搜尋時，找到最大的利潤。這裡是預先處理一個額外的陣列 $\textit{max\_profit}$ 來存儲前 $i$ 個工作的最大利潤，這樣在每次二分搜尋後，只需要 $O(1)$ 的時間複雜度即可找到最大利潤。

複雜度分析

時間複雜度： $O(n \log n + m \log n)$ ，排序的時間複雜度為 $O(n \log n)$ ，每次二分搜尋的時間複雜度為 $O(\log n)$ ，總共有 $m$ 次二分搜尋。
空間複雜度： $O(n)$ ，用於存儲排序後的工作，以及前 $i$ 個工作的最大利潤。

class Solution:
    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:
        n, m = len(difficulty), len(worker)
        tasks = sorted(zip(difficulty, profit)) # sort by difficulty
        max_profit = [0] * (n) # max_profit[i] = max profit of tasks[0:i+1]
        max_profit[0] = tasks[0][1]
        for i in range(1, n):
            max_profit[i] = max(max_profit[i-1], tasks[i][1])
        ans = 0
        for ability in worker:
            idx = bisect_right(tasks, (ability, float("inf"))) - 1 # find the last task that can be done
            ans += max_profit[idx] if idx >= 0 else 0
        return ans

class Solution {
public:
    int maxProfitAssignment(vector<int>& difficulty, vector<int>& profit, vector<int>& worker) {
        int n = difficulty.size(), m = worker.size();
        vector<pair<int, int>> tasks;
        for (int i = 0; i < n; i++) tasks.push_back({difficulty[i], profit[i]});
        sort(tasks.begin(), tasks.end()); // sort by difficulty
        vector<int> max_profit(n, 0); // max_profit[i] = max profit of tasks[0:i+1]
        max_profit[0] = tasks[0].second;
        for (int i = 1; i < n; i++) {
            max_profit[i] = max(max_profit[i-1], tasks[i].second);
        }
        int ans = 0;
        for (int w : worker) {
            int idx = upper_bound(tasks.begin(), tasks.end(), make_pair(w, INT_MAX)) - tasks.begin() - 1; // find the last task that can be done
            ans += idx >= 0 ? max_profit[idx] : 0;
        }
        return ans;
    }
};