leetcode
leetcode 1801 ~ 1850
你可以安排的最多任务数目

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

难度:

标签:

题目描述

代码结果

运行时间: 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函数中进行任务分配?
在二分搜索中,中间值mid代表当前尝试分配任务的工人的起始偏移量。这意味着从数组中的mid位置开始,向后的所有工人都可能被用来完成任务。在check函数中,使用这个起始偏移量来确定哪些工人可用,从而根据任务的难度和工人的能力(包括是否使用药丸增强)来决定任务是否可以被完成。如果从mid开始的所有工人配合药丸的使用可以完成任务列表中的足够多任务,则认为这个mid是有效的,二分搜索会尝试更小的mid值以寻找可能的最大任务完成数。
🦆
check函数中如何决定使用或不使用药丸?具体的逻辑是怎样的?
在check函数中,决定是否使用药丸的逻辑基于当前工人的力量与所分配任务的力量需求之间的比较。如果当前工人的力量(即使是已经使用药丸增强过的工人)不足以完成当前任务,且还有剩余的药丸,则会考虑使用一粒药丸。药丸的使用会将工人的力量临时增加一定数值(strength),然后重新评估是否能完成任务。如果使用了药丸后仍不能完成任务或者没有剩余药丸,算法会判断为这个mid值不可行。
🦆
当一个工人使用了药丸后,他的力量值增加了strength,但如果这仍不足以完成当前的任务,算法是如何处理的?
如果工人使用药丸后力量增加了strength,但增加后的力量仍不足以完成当前任务,则该任务实际上是无法被当前的工人完成的。在这种情况下,算法会继续寻找下一个可用的工人或继续使用其他药丸增强的工人尝试完成该任务。如果没有更多的工人或药丸可用,这将导致当前的mid值失败,表示从mid开始的工人数无法完成足够多的任务,二分搜索会调整范围尝试一个更大的mid值。

相关问题