LeetCode 826 Most Profit Assigning Work

傳送門

題目分析

We have jobs: difficulty[i] is the difficulty of the ith job, and profit[i] is the profit of the ith job.

Now we have some workers. worker[i] is the ability of the ith worker, which means that this worker can only complete a job with difficulty at most worker[i].

Every worker can be assigned at most one job, but one job can be completed multiple times.

For example, if 3 people attempt the same job that pays 1,thenthetotalprofitwillbe1,thenthetotalprofitwillbe3. If a worker cannot complete any job, his profit is $0.

What is the most profit we can make?

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 profit of [20,20,30,30] seperately.

Notes:

• 1 <= difficulty.length = profit.length <= 10000
• 1 <= worker.length <= 10000
• difficulty[i], profit[i], worker[i] are in range [1, 10^5]

給定工作難度，工資，工人的能力，三個數組，可能每份工作可以重復使用，計算最大利潤。

思考

首先數據量很大，直接暴力寫是不太可能了，可以先對難度和利潤進行排序，這樣worker的遍歷時就可以及時停止遍歷了，還有就是使用HashMap記錄已經有了的worker數據進行重用，因為能力相同的工人可以得到的最大利潤也是相同的。

代碼實現

import java.util.HashMap;class Solution {public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {if (difficulty.length == 0 || worker.length == 0) {return 0;}int result = 0;// 變形快排，將diffifulty和profit綁在一起排序quickSort(difficulty, profit, 0, difficulty.length - 1);HashMap<Integer, Integer> map = new HashMap<>();for (int abi : worker) {// find work for personif (map.containsKey(abi)) {result += map.get(abi);continue;}int money = 0;for (int i = 0; i < difficulty.length; ++i) {if (difficulty[i] <= abi) {money = Math.max(money, profit[i]);} else {break;}}result += money;map.put(abi, money);}return result;}// 快排變形，以diffi為主鍵，對pro和diffi同時排序void quickSort(int[] diffi, int[] pro, int start, int end) {if (start >= end) {return;}int s = start, e = end;int dmid = diffi[s];int pmid = pro[s];while (s < e) {while (s < e && diffi[e] >= dmid) {--e;}swap(diffi, s, e);swap(pro, s, e);while (s < e && diffi[s] <= dmid) {++s;}swap(diffi, s, e);swap(pro, s, e);}diffi[s] = dmid;pro[s] = pmid;quickSort(diffi, pro, start, s - 1);quickSort(diffi, pro, s + 1, end);}void swap(int[] arr, int a, int b) {int t = arr[a];arr[a] = arr[b];arr[b] = t;} }

感想

代碼時間復雜度太慘了，不知道可以怎么改進啊？

總結

以上是生活随笔為你收集整理的LeetCode 826 Most Profit Assigning Work的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。