2071. 你可以安排的最多任务数目

题目链接2071. 你可以安排的最多任务数目 - 力扣LeetCode题目描述给你n个任务和m个工人。每个任务需要一定的力量值才能完成需要的力量值保存在下标从 0 开始的整数数组tasks中第i个任务需要tasks[i]的力量才能完成。每个工人的力量值保存在下标从 0 开始的整数数组workers中第j个工人的力量值为workers[j]。每个工人只能完成 一个 任务且力量值需要 大于等于 该任务的力量要求值即workers[j] tasks[i]。除此以外你还有pills个神奇药丸可以给 一个工人的力量值 增加strength。你可以决定给哪些工人使用药丸但每个工人 最多 只能使用 一片 药丸。给你下标从 0 开始的整数数组tasks和workers以及两个整数pills和strength请你返回 最多 有多少个任务可以被完成。题目示例示例 1 :输入tasks [3,2,1], workers [0,3,3], pills 1, strength 1 输出3 解释 我们可以按照如下方案安排药丸 - 给 0 号工人药丸。 - 0 号工人完成任务 20 1 1 - 1 号工人完成任务 13 2 - 2 号工人完成任务 03 3示例 2 :输入tasks [5,4], workers [0,0,0], pills 1, strength 5 输出1 解释 我们可以按照如下方案安排药丸 - 给 0 号工人药丸。 - 0 号工人完成任务 00 5 5解题思路问题描述给定两个数组tasks和workers分别表示任务难度和工人能力值。工人可以吃药吃药后能力值增加strength。目标是在最多使用pills颗药的情况下分配任务给工人使得完成的任务数最大。关键观察为了最大化完成任务数应该让最强的工人完成最难的任务贪心策略。吃药的使用应该尽量用在最需要的时候即工人不吃药无法完成任务时。可以通过二分查找来确定最多能完成的任务数。算法选择排序首先对tasks和workers进行排序方便后续处理。二分查找在可能的最大任务数范围内进行二分查找确定最多能完成的任务数。贪心策略在check方法中使用双端队列记录当前可以完成的任务优先让工人不吃药完成最简单的任务必须时才吃药完成最难的任务。题解代码classSolution{publicintmaxTaskAssign(int[]tasks,int[]workers,intpills,intstrength){// 对任务和工人数组进行排序方便后续处理Arrays.sort(tasks);Arrays.sort(workers);// 使用二分查找确定最多能完成的任务数intleft0;// 最小可能完成的任务数intrightMath.min(tasks.length,workers.length)1;// 最大可能完成的任务数 1while(left1right){intmid(leftright)1;// 无符号右移相当于 (left right) / 2// 检查是否能完成 mid 个任务if(check(tasks,workers,pills,strength,mid)){leftmid;// 可以完成 mid 个任务尝试更大的值}else{rightmid;// 不能完成 mid 个任务尝试更小的值}}returnleft;// 返回最大能完成的任务数}privatebooleancheck(int[]tasks,int[]workers,intpills,intstrength,intk){// 使用双端队列记录当前可以完成的任务DequeIntegervalidTasksnewArrayDeque();inti0;// 指向 tasks 的指针// 遍历最强的 k 个工人for(intjworkers.length-k;jworkers.length;j){intwworkers[j];// 当前工人的能力值// 将当前工人吃药后能完成的任务加入队列while(iktasks[i]wstrength){validTasks.addLast(tasks[i]);i;}// 如果没有任务可以完成直接返回 falseif(validTasks.isEmpty()){returnfalse;}// 如果当前工人不吃药就能完成最简单的任务if(wvalidTasks.peekFirst()){validTasks.pollFirst();// 完成最简单的任务continue;}// 必须吃药才能完成任务if(pills0){// 没有药了无法完成任务returnfalse;}pills--;// 消耗一颗药validTasks.pollLast();// 完成最难的任务贪心策略}returntrue;// 所有工人都能完成任务}}复杂度分析时间复杂度排序Arrays.sort的时间复杂度为O(n log n)和O(m log m)其中n和m分别是tasks和workers的长度。二分查找最多进行O(log(min(n, m)))次查找。每次** ****check**O(k)其中k是当前尝试的任务数。总时间复杂度O((n log n) (m log m) (min(n, m) * log(min(n, m))))可以简化为O((n m) log (n m))。空间复杂度排序Arrays.sort使用O(log n)或O(log m)的栈空间取决于具体实现。双端队列最多存储O(k)个元素其中k是最大可能完成的任务数。总空间复杂度O(min(n, m))。