文章目录题目标题和出处难度题目描述要求示例数据范围解法思路和算法代码复杂度分析题目标题和出处标题安排工作以达到最大收益出处826. 安排工作以达到最大收益难度5 级题目描述要求有n \texttt{n}n个工作和m \texttt{m}m个工人。给定三个数组difficulty \texttt{difficulty}difficulty、profit \texttt{profit}profit和worker \texttt{worker}worker其中difficulty[i] \texttt{difficulty[i]}difficulty[i]表示第i \texttt{i}i个工作的难度profit[i] \texttt{profit[i]}profit[i]表示第i \texttt{i}i个工作的收益。worker[j] \texttt{worker[j]}worker[j]是第j \texttt{j}j个工人的能力即该工人只能完成难度小于等于worker[j] \texttt{worker[j]}worker[j]的工作。每个工人最多只能安排一个工作但是一个工作可以完成多次。例如如果3 \texttt{3}3个工人都尝试完成一份报酬为1 \texttt{1}1的同样工作那么总收益为3 \texttt{3}3。如果一个工人不能完成任何工作他的收益为0 \texttt{0}0。返回在把工人分配到工作岗位后能获得的最大利润。示例示例 1输入difficulty [2,4,6,8,10], profit [10,20,30,40,50], worker [4,5,6,7] \texttt{difficulty [2,4,6,8,10], profit [10,20,30,40,50], worker [4,5,6,7]}difficulty [2,4,6,8,10], profit [10,20,30,40,50], worker [4,5,6,7]输出100 \texttt{100}100解释工人被分配的工作难度是[4,4,6,6] \texttt{[4,4,6,6]}[4,4,6,6]分别获得[20,20,30,30] \texttt{[20,20,30,30]}[20,20,30,30]的收益。示例 2输入difficulty [85,47,57], profit [24,66,99], worker [40,25,25] \texttt{difficulty [85,47,57], profit [24,66,99], worker [40,25,25]}difficulty [85,47,57], profit [24,66,99], worker [40,25,25]输出0 \texttt{0}0数据范围n difficulty.length profit.length \texttt{n} \texttt{difficulty.length} \texttt{profit.length}ndifficulty.lengthprofit.lengthm worker.length \texttt{m} \texttt{worker.length}mworker.length1 ≤ n, m ≤ 10 4 \texttt{1} \le \texttt{n, m} \le \texttt{10}^\texttt{4}1≤n, m≤1041 ≤ difficulty[i], profit[i], worker[i] ≤ 10 5 \texttt{1} \le \texttt{difficulty[i], profit[i], worker[i]} \le \texttt{10}^\texttt{5}1≤difficulty[i], profit[i], worker[i]≤105解法思路和算法由于一个工作可以完成多次因此给每个工人安排的工作是独立的。根据贪心思想为了获得最大利润应将每个工人的收益最大化因此应给每个工人安排其能完成的收益最大的工作。使用二维数组difficultyProfit \textit{difficultyProfit}difficultyProfit存储每个工作的难度和收益对于第i ii份工作difficultyProfit [ i ] [ 0 ] \textit{difficultyProfit}[i][0]difficultyProfit[i][0]和difficultyProfit [ i ] [ 1 ] \textit{difficultyProfit}[i][1]difficultyProfit[i][1]分别表示其难度和收益。将difficultyProfit \textit{difficultyProfit}difficultyProfit按照以下规则排序。当难度不同时按照难度升序排序。当难度相同时按照收益降序排序。排序之后正向遍历difficultyProfit \textit{difficultyProfit}difficultyProfit对于i 0 i 0i0将difficultyProfit [ i ] [ 1 ] \textit{difficultyProfit}[i][1]difficultyProfit[i][1]更新为difficultyProfit [ i ] [ 1 ] \textit{difficultyProfit}[i][1]difficultyProfit[i][1]和difficultyProfit [ i − 1 ] [ 1 ] \textit{difficultyProfit}[i - 1][1]difficultyProfit[i−1][1]中的最大值。更新之后difficultyProfit [ i ] [ 1 ] \textit{difficultyProfit}[i][1]difficultyProfit[i][1]表示难度不超过difficultyProfit [ i ] [ 0 ] \textit{difficultyProfit}[i][0]difficultyProfit[i][0]的工作的最大收益。此时数组difficultyProfit \textit{difficultyProfit}difficultyProfit中包含每种工作难度对应的最大收益需要对每个工人寻找难度不超过该工人的能力的工作的最大收益。将数组worker \textit{worker}worker按升序排序然后同时反向遍历数组difficultyProfit \textit{difficultyProfit}difficultyProfit和数组worker \textit{worker}worker两个数组的下标分别是i ii和j jj初始时i n − 1 i n - 1in−1j m − 1 j m - 1jm−1。每一步执行如下操作。当i ≥ 0 i \ge 0i≥0且difficultyProfit [ i ] [ 0 ] worker [ j ] \textit{difficultyProfit}[i][0] \textit{worker}[j]difficultyProfit[i][0]worker[j]时表示当前工作难度超过工人worker [ j ] \textit{worker}[j]worker[j]的能力因此将i ii减1 11直到i 0 i 0i0或difficultyProfit [ i ] [ 0 ] ≤ worker [ j ] \textit{difficultyProfit}[i][0] \le \textit{worker}[j]difficultyProfit[i][0]≤worker[j]。当i ≥ 0 i \ge 0i≥0时可以将难度不超过difficultyProfit [ i ] [ 0 ] \textit{difficultyProfit}[i][0]difficultyProfit[i][0]的工作安排给工人worker [ j ] \textit{worker}[j]worker[j]当前工人的最大收益是difficultyProfit [ i ] [ 1 ] \textit{difficultyProfit}[i][1]difficultyProfit[i][1]将当前工人的最大收益加到总收益中。将j jj减1 11继续遍历其余工人。当i 0 i 0i0或j 0 j 0j0时表示没有剩余的工作可以分配给工人或者所有的工人都被分配工作结束操作此时即可得到最大利润。代码classSolution{publicintmaxProfitAssignment(int[]difficulty,int[]profit,int[]worker){intmaxProfit0;intndifficulty.length,mworker.length;int[][]difficultyProfitnewint[n][2];for(inti0;in;i){difficultyProfit[i][0]difficulty[i];difficultyProfit[i][1]profit[i];}Arrays.sort(difficultyProfit,(a,b)-{if(a[0]!b[0]){returna[0]-b[0];}else{returnb[1]-a[1];}});for(inti1;in;i){difficultyProfit[i][1]Math.max(difficultyProfit[i][1],difficultyProfit[i-1][1]);}Arrays.sort(worker);for(intin-1,jm-1;i0j0;j--){while(i0difficultyProfit[i][0]worker[j]){i--;}if(i0){maxProfitdifficultyProfit[i][1];}}returnmaxProfit;}}复杂度分析时间复杂度O ( n log ⁡ n m log ⁡ m ) O(n \log n m \log m)O(nlognmlogm)其中n nn是数组difficulty \textit{difficulty}difficulty和profit \textit{profit}profit的长度m mm是数组worker \textit{worker}worker的长度。创建二维数组difficultyProfit \textit{difficultyProfit}difficultyProfit需要O ( n ) O(n)O(n)的时间将二维数组difficultyProfit \textit{difficultyProfit}difficultyProfit排序并遍历需要O ( n log ⁡ n ) O(n \log n)O(nlogn)的时间将数组worker \textit{worker}worker排序需要O ( m log ⁡ m ) O(m \log m)O(mlogm)的时间反向遍历两个数组需要O ( n m ) O(n m)O(nm)的时间因此时间复杂度是O ( n log ⁡ n m log ⁡ m ) O(n \log n m \log m)O(nlognmlogm)。空间复杂度O ( n log ⁡ m ) O(n \log m)O(nlogm)其中n nn是数组difficulty \textit{difficulty}difficulty和profit \textit{profit}profit的长度m mm是数组worker \textit{worker}worker的长度。创建二维数组difficultyProfit \textit{difficultyProfit}difficultyProfit需要O ( n ) O(n)O(n)的空间二维数组difficultyProfit \textit{difficultyProfit}difficultyProfit中的元素是数组因此将二维数组difficultyProfit \textit{difficultyProfit}difficultyProfit排序需要O ( n ) O(n)O(n)的空间将数组worker \textit{worker}worker排序需要O ( log ⁡ m ) O(\log m)O(logm)的空间因此空间复杂度是O ( n log ⁡ m ) O(n \log m)O(nlogm)。