华为OD 机试 2025-高效的任务规划

✅ 题目描述

阿里工程团队负责配置一批任务机器，有 n 台机器（编号从 1 到 n）。每台机器必须配置一次才能开始运行工作。配置只能串行进行，但机器配置完后即可并行运行任务。

每台机器有两个时间参数：

• B[i]：第 i 台机器的配置时间；
• J[i]：第 i 台机器的运行时间。

请你编写程序，输出每组任务的最短总完成时间（即最后一台机器完成工作的时间），你可以自定义配置顺序。

✅ 输入描述

• 第 1 行输入一个整数 M（1 < M ≤ 10），表示任务组数。

• 每组任务格式如下：

  • 第 1 行输入一个整数 N（0 < N ≤ 1000），表示机器数。
  • 接下来的 N 行，每行两个整数 B[i] 和 J[i]（0 ≤ B[i], J[i] ≤ 10000），表示第 i 台机器的配置时间与运行时间。

✅ 输出描述

对于每组任务，输出一个整数，表示最短完成时间，每个结果占一行。

✅ 示例输入

2
2
1 1
2 2
3
1 1
2 2
3 3

✅ 示例输出

5
9

✅ 解题思路解析（贪心策略）

核心思想：配置时间不可并行 → 要选择一个顺序配置所有机器。而机器运行时间可以并行 → 应优先配置运行时间长的机器，使它们尽早开始执行任务。

策略：

1. 将所有机器按运行时间 J[i] 从大到小排序；

2. 依次配置每台机器：

   • 累加配置时间；
   • 记录当前机器的 “结束时间” = 累计配置时间 + 自身运行时间；
   • 更新最大结束时间，即最终完成时间。

✅ Python 实现

def solve_method(task_groups):
    results = []
    for machines in task_groups:
        # 贪心策略：运行时间大的优先配置
        machines.sort(key=lambda x: -x[1])

        config_time = 0
        max_finish_time = 0
        for b, j in machines:
            config_time += b
            max_finish_time = max(max_finish_time, config_time + j)

        results.append(max_finish_time)
    return results


# 示例测试
if __name__ == '__main__':
    tasks = [
        [(1, 1), (2, 2)],
        [(1, 1), (2, 2), (3, 3)]
    ]
    for res in solve_method(tasks):
        print(res)

✅ Java 实现

import java.util.*;

public class MachineScheduler {
    public static List<Integer> solve(List<List<int[]>> taskGroups) {
        List<Integer> result = new ArrayList<>();
        for (List<int[]> machines : taskGroups) {
            machines.sort((a, b) -> b[1] - a[1]); // 按运行时间降序

            int configTime = 0, maxTime = 0;
            for (int[] machine : machines) {
                configTime += machine[0];
                maxTime = Math.max(maxTime, configTime + machine[1]);
            }
            result.add(maxTime);
        }
        return result;
    }

    public static void main(String[] args) {
        List<List<int[]>> tasks = new ArrayList<>();
        tasks.add(Arrays.asList(new int[]{1, 1}, new int[]{2, 2}));
        tasks.add(Arrays.asList(new int[]{1, 1}, new int[]{2, 2}, new int[]{3, 3}));

        for (int res : solve(tasks)) {
            System.out.println(res);
        }
    }
}

✅ JavaScript 实现

function solve(taskGroups) {
    const results = [];

    for (const machines of taskGroups) {
        machines.sort((a, b) => b[1] - a[1]); // 按运行时间降序

        let configTime = 0;
        let maxTime = 0;

        for (const [b, j] of machines) {
            configTime += b;
            maxTime = Math.max(maxTime, configTime + j);
        }

        results.push(maxTime);
    }

    return results;
}

// 示例测试
const tasks = [
    [[1, 1], [2, 2]],
    [[1, 1], [2, 2], [3, 3]]
];

solve(tasks).forEach(res => console.log(res));

✅ 总结