华为OD机试 - 项目排期 - 贪心算法（Java 2024 C卷 200分）

在这里插入图片描述

华为OD机试 2024C卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（A卷+B卷+C卷）》。

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

项目组共有N个开发人员，项目经理接到了M个独立的需求，每个需求的工作量不同，且每个需求只能由一个开发人员独立完成，不能多人合作。

假定各个需求直接无任何先后依赖关系，请设计算法帮助项目经理进行工作安排，使整个项目能用最少的时间交付。

二、输入描述

第一行输入为M个需求的工作量，单位为天，用逗号隔开。例如：X1 X2 X3 … Xm 表示共有M个需求，每个需求的工作量分别为X1天，X2天…Xm天。其中0<M<30；0<Xm<200 第二行输入为项目组人员数量N 例如： 5 表示共有5名员工，其中0<N<10

三、输出描述

最快完成所有工作的天数例如： 25 表示最短需要25天能完成所有工作。

四、解题思路

这个问题是典型的“负载均衡”问题，其中的目标是最小化完成所有任务的最大时间。在这个问题中，我们需要将M个任务（需求），每个有不同的工作量，分配给N个开发人员，使得所有工作被完成的总时间最小。

一个有效的方法是使用“最短处理时间优先”（SPT，Shortest Processing Time first）策略，结合“最长任务优先分配”（Largest Task First allocation）以及“贪心算法”，使得总体完成时间最短。

具体步骤：

任务排序：首先按照工作量从大到小对需求进行排序。
初始化工作量数组：创建一个数组（或列表），用以记录每位开发人员当前的工作量。
贪心分配任务：依次将最大的任务分配给当前工作量最小的开发人员。

通过这种方式，我们尽可能保证每个人的负载都接近平均，但尽量让工作量较大的任务先分配，从而尽早开始执行耗时较长的任务。

五、Java算法源码

public class OdTest01 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取工作量和员工数
        String[] workloadStr = scanner.nextLine().split(" ");
        int[] workloads = Arrays.stream(workloadStr).mapToInt(Integer::parseInt).toArray();
        int numEmployees = Integer.parseInt(scanner.nextLine());

        // 计算最短完成时间
        int minDays = calculateMinimumDays(workloads, numEmployees);
        System.out.println(minDays);
    }

    private static int calculateMinimumDays(int[] workloads, int numEmployees) {
        // 将任务按照工作量从大到小排序
        Arrays.sort(workloads);
        // 初始化员工工作天数数组
        int[] employeeLoad = new int[numEmployees];

        // 从最大工作量任务开始分配
        for (int i = workloads.length - 1; i >= 0; i--) {
            int minLoadIndex = 0;
            // 找到当前工作量最小的员工
            for (int j = 1; j < numEmployees; j++) {
                if (employeeLoad[j] < employeeLoad[minLoadIndex]) {
                    minLoadIndex = j;
                }
            }
            // 分配任务给该员工
            employeeLoad[minLoadIndex] += workloads[i];
        }

        // 找出最大的工作量，即为完成所有任务的最少天数
        int maxDays = 0;
        for (int load : employeeLoad) {
            maxDays = Math.max(maxDays, load);
        }
        return maxDays;
    }
}