題目敘述 Most Profit Assigning Work
公司裡有n位員工，m件任務。
每位員工的能力記錄在worker陣列。每個任務對應的能力要求和獲利紀錄在difficulty 和profit陣列。
不同的員工可以做同樣的任務。
請問怎麼分配任務可以得到整體最大獲利?
測試範例
Example 1:
Input: difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]
Output: 100
Explanation: Workers are assigned jobs of difficulty [4,4,6,6] and they get a profit of [20,20,30,30] separately.
Example 2:
Input: difficulty = [85,47,57], profit = [24,66,99], worker = [40,25,25]
Output: 0
難度都超過員工能力值，沒有合適的任務。
約束條件
Constraints:
n == difficulty.lengthn == profit.length
總共有n個任務
m == worker.length
總共有m位員工。
1 <= n, m <= 10^4
參數n和m都介於1~一萬之間。
1 <= difficulty[i], profit[i], worker[i] <= 10^5
任務難度、任務獲利、員工能力都介於1~十萬之間。
觀察 人盡其才 Greedy策略
最大獲利 直覺想到的就是盡可能挑能力範圍內，獲利大的任務來做。
先針對每個任務依據難度從小到大排序。
每位員工也依據能力從小到大排序。
接著，針對每位員工，在他的能力範圍內，挑選獲利最大的任務來做。
這邊的思想就是(Greedy策略)局部最佳化，進一步帶來整體的最佳化。
演算法 人盡其才 Greedy策略
承接觀察點的思考。
每個任務依據難度從小到大排序。
每位員工也依據能力從小到大排序。
針對每位員工，在他的能力範圍內，挑選獲利最大的任務來做。
程式碼 人盡其才 Greedy策略
class Solution:
def maxProfitAssignment(self, difficulty : List[int], profit: List[int], worker: List[int]) -> int:
# sort jobs by (difficulty, profit) pair
jobs = sorted(zip(difficulty , profit))
# sort worker by ability from small to large
worker.sort()
total_profit, job_index, max_profit = 0,0,0
# Each worker choose the job which has most profit and within ability.
for ability in worker:
while job_index < len(jobs) and jobs[job_index][0] <= ability:
max_profit = max(max_profit, jobs[job_index][1])
job_index+=1
total_profit += max_profit
return total_profit
複雜度分析
時間複雜度: O( n log n + m log m)
排序任務耗費O( n log n)
排序員工耗費O( m log m)
分配任務耗費O( m + n)
空間複雜度: O(n)
重新產生一個新的任務的(難度, 獲利)陣列，所需空間為O(n)
關鍵知識點 Greedy策略
針對每位員工，在他的能力範圍內，挑選獲利最大的任務來做。
這邊的思想就是(Greedy策略)局部最佳化，進一步帶來整體的最佳化。
