最大獲利的工作安排 Most Profit Assigning Work_Leetcode #826 Greedy策略

Campaign Creators on Unsplash

題目敘述 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.length
• n == 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策略)局部最佳化，進一步帶來整體的最佳化。

Reference

[1] Most Profit Assigning Work - LeetCode