你可以安排的最多任务数目
难度:
标签:
题目描述
代码结果
运行时间: 430 ms, 内存: 24.4 MB
import java.util.Arrays;
import java.util.stream.IntStream;
/**
* This class provides a solution to the problem of assigning tasks to workers
* with the help of pills to increase workers' strength when needed, utilizing Java Streams.
*/
public class TaskAssignmentStream {
/**
* Determines the maximum number of tasks that can be completed.
*
* @param tasks Array of task strength requirements
* @param workers Array of worker strengths
* @param pills Number of pills available
* @param strength The strength a pill adds to a worker
* @return Maximum number of tasks that can be completed
*/
public int maxTaskAssign(int[] tasks, int[] workers, int pills, int strength) {
Arrays.sort(tasks);
Arrays.sort(workers);
return IntStream.iterate(0, i -> i + 1)
.limit(Math.min(tasks.length, workers.length))
.map(i -> Math.min(tasks.length, workers.length) - i)
.filter(mid -> canComplete(tasks, workers, mid, pills, strength))
.findFirst()
.orElse(0);
}
/**
* Helper method to check if a certain number of tasks can be completed.
*
* @param tasks Sorted array of task strength requirements
* @param workers Sorted array of worker strengths
* @param k Number of tasks to complete
* @param pills Number of pills available
* @param strength The strength a pill adds to a worker
* @return True if k tasks can be completed, false otherwise
*/
private boolean canComplete(int[] tasks, int[] workers, int k, int pills, int strength) {
int[] effectiveWorkers = Arrays.copyOfRange(workers, workers.length - k, workers.length);
int pillCount = pills;
return IntStream.range(0, k).map(i -> k - 1 - i)
.allMatch(i -> effectiveWorkers[i] >= tasks[i] || (pillCount > 0 && effectiveWorkers[i] + strength >= tasks[i] && (pillCount-- > 0)));
}
}
解释
方法:
此题解使用二分搜索和贪心算法的组合来解决问题。首先,对任务和工人的力量数组进行排序。利用二分搜索尝试找到最大数量的任务可以被完成。对于二分搜索的每个中点,使用check函数来验证是否可以完成至少这么多任务。check函数通过维护两个队列(一个用于已使用药丸增强的工人,一个用于未使用药丸的工人)来尝试分配工人以完成任务,如果任务的力量要求高于当前工人(包括加强后的工人)的力量,就尝试使用药丸。如果不能使用更多的药丸且没有足够力量的工人,则返回失败。通过这种方式,check函数可以判断出在当前二分搜索的中间值下,能否完成任务。最终,二分搜索确定可以完成任务的最大数量。
时间复杂度:
O(m log m + n log n)
空间复杂度:
O(m)
代码细节讲解
🦆
为什么需要将任务和工人的力量数组进行排序?这对算法的效率和结果有什么影响?
▷🦆
在二分搜索中,中间值mid代表什么含义?如何根据mid值在check函数中进行任务分配?
▷🦆
check函数中如何决定使用或不使用药丸?具体的逻辑是怎样的?
▷🦆
当一个工人使用了药丸后,他的力量值增加了strength,但如果这仍不足以完成当前的任务,算法是如何处理的?
▷