通过率 90% · 提交 10 · 通过 9
在企业数据中台或自动化构建系统中,一个大型任务集由成百上千个子任务组成。 有的任务之间存在严格依赖关系,为提升效率,没有相互依赖关系的任务将会被系统并行(同时)执行。 你需要编写一个算法:在给定所有任务的执行时间,以及它们之间的依赖关系后,评估出整个数据流水线完全运行结束所需的最短总时间。
这类题属于算法机考高频题型中「200分 / 华为OD」方向的高频题型,通常考察对「200分 / 华为OD」的建模能力与边界条件处理。掌握本题的解题思路后,可举一反三应对同类真题方向,稳步提升机考通过率。
times:一个二维数组,其中 times[i] = [task_id, duration],表示任务 task_id 执行所需的耗时为 duration 分钟。 dependencies:一个二维数组,其中 dependencies[i] = [A, B] 表示任务 A 必须在任务 B 开始之前完成;输入保证不存在环形依赖。
数据范围: 1 <= n <= 10^4,n 为 times 的长度,任务编号 task_id 为 1 ~ n 且互不相同 1 <= duration <= 10^4 0 <= dependencies.length <= 10^5,1 <= A, B <= n,A != B
请计算完成给定任务的最少时间。
示例 1
输入示例
1,3 2,2 3,5 4,1 5,4 1,3 2,3 3,4 3,5
输出示例
12
任务 1 和 2 没有任何前置依赖,它们在第 0 分钟同时并行启动。 任务 2 在第 2 分钟完成,但任务 3 还需要等待任务 1(耗时 3 分钟)完成。 任务 3 在第 3 分钟启动,并在第 8 分钟(3 + 5)完成。 任务 4 和 5 在第 8 分钟同时并行启动。 任务 4 在第 9 分钟完成,任务 5 在第 12 分钟(8 + 4)完成。 整个流水线的瓶颈在任务 5,所以总耗时为 12。
示例 2
输入示例
1,10 2,5 3,8
输出示例
10
没有任何前置条件,任务 1、2、3 在第 0 分钟同时并行启动。 任务 2 在第 5 分钟完成。 任务 3 在第 8 分钟完成。 任务 1 在第 10 分钟完成。 这批任务的总耗时仅仅取决于耗时最长的那单个任务(即任务 1),所以总耗时为 10。
时间限制 1000 ms · 内存限制 256 MB
本平台为独立第三方培训机构,与华为技术有限公司无任何关联;课程的服务内容与权益以购买协议为准,学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述,相关商标归各自权利人所有。
登录后可查看你在本题的历史提交,以及每次的各用例通过情况。
© 2026 广州慕课网络科技有限公司 · 吴师兄学算法官网 版权所有