前往
大廳
主題

LeetCode - 826. Most Profit Assigning Work 解題心得

Not In My Back Yard | 2023-01-27 12:00:00 | 巴幣 0 | 人氣 162

題目連結:


題目意譯:
你有 n 件工作和 m 位工人。你被給定三個陣列:difficulty 、 profit 和 worker,其中:
difficulty[i] 和 profit[i] 代表著第 i 件工作的難度以及獲益,而
worker[j] 為第 j 位工人的能力值(即第 j 位工人只能完成難度最高為 worker[j] 的工作)。

所有工人最多可以分配到一件工作上,但是一件工作可以被完成複數次。

例如,如果三位工人都試著處理獲益 $1 的工作,則總獲益為 $3。如果一位工人不能完成任何工作,則他的獲益為 $0。

回傳給工人分配工作之後我們能達到的最大獲益。

限制:
n == difficulty.length
n == profit.length
m == worker.length
1 ≦ n, m ≦ 10 ^ 4
1 ≦ difficulty[i], profit[i], worker[i] ≦ 10 ^ 5



範例測資:
範例 1:
輸入: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
輸出: 100
解釋: 工人們各自被分配到難度為 [4,4,6,6] 的工作,而他們各自的獲益為 [20,20,30,30]。

範例 2:
輸入: difficulty = [85,47,57], profit = [24,66,99], worker = [40,25,25]
輸出: 0


解題思維:
先把每一位工人根據能力值(worker)由大排到小,而每個工作也先按照利潤(profit)大到小排,利潤一樣的再按難度(difficulty)大到小排。

然後先讓最有能力的工人(此時為 worker[0])去找利潤最大且可以被他完成的工作(例如說是根據上列條件排序後的第 j 個工作)。

接著掃過剩下的工人,由於我們把能力值由大到小排,因此每一位工人他可以完成且利潤最大的「第 j 個工作」之 j 值必定大於等於前一位工人的 j 值(畢竟如果前一位完成不了 j - 1 這份工作,當然現在這位也不能)。

因此把每一位工人找到的工作(如果有的話)之利潤加總即為所求最大利潤。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作