会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（华为校招机考题库），可解锁完整内容。

购买题库开通会员

解题思路

任务数量较小，可以使用回溯枚举所有满足依赖关系的任务执行顺序。

核心算法是拓扑顺序枚举 + 最早可行时间调度：

每个任务用一个二进制状态表示所需的 $NPU$ 卡集合。

在回溯过程中维护：

P5106.第3题-昇腾NPU协同调度系统

1000ms

Tried: 9

Accepted: 8

Difficulty: 9

所属公司 : 华为

算法与标签>DFS

题目内容

设计一个调度系统管理昇腾 $NPU$ 上的训练任务，需满足以下条件：

任务属性（每个任务包含 $3$ 个维度）

$npus$ ：所需 $NPU$ 卡编号列表
$duration$ ：执行需要的时间片数
$depend_on$ ：必须在该任务前完成的任务 $ID$ （只会依赖 $0$ 或者 $1$ 个上游任务）

调度规则

每张 $NPU$ 卡同一时间只能执行一个任务
任务必须在前置任务完成后才能开始
时间片为正整数，多个满足条件的任务可并行启动，不可抢占已分配任务
可能存在多种调度方案，需要选出全部任务结束耗时最短的一种

用例保证存在可调度方案（不存在任务间循环依赖），输出所有任务全部完成需要的最短时间。

输入描述

第 $1$ 行， $NPU$ 卡总数（ $1<=NPU卡总数<=10$ ），总任务数量（ $1<=总任务数量<=8$ ），如： $4$ $2$

第 $2$ 行，【第 $2-4$ 行第 $0$ 个任务】，任务 $0$ 依赖的 $npu$ 列表（空格分割），如： $0$ $1$

第 $3$ 行，【第 $2-4$ 行第 $0$ 个任务】，任务 $0$ 持续时间，如： $5$

第 $4$ 行，【第 $2-4$ 行第 $0$ 个任务】，任务 $0$ 依赖的上游任务 $ID$ （无依赖时固定为 $-1$ ），如： $1$

第 $5$ 行，【第 $5-7$ 行第 $1$ 个任务】，任务 $1$ 依赖的 $npu$ 列表（空格分割），如： $1$ $2$

第 $6$ 行，【第 $5-7$ 行第 $1$ 个任务】，任务 $1$ 持续时间，如： $4$

第 $7$ 行，【第 $5-7$ 行第 $1$ 个任务】，任务 $1$ 依赖的上游任务 $ID$ （无依赖时固定为 $-1$ ），如： $0$

……，如果存在更多任务， $3$ 行一组进行输入，任务 $i$ 依赖的 $npu$ 列表（空格分割），如： $1$ $2$

……，如果存在更多任务， $3$ 行一组进行输入，任务 $i$ 持续时间，如： $4$

……，如果存在更多任务， $3$ 行一组进行输入，任务 $i$ 依赖的上游任务 $ID$ （无依赖时固定为 $-1$ ），如： $0$

注意：题目保证输入合法，无需校验输入

输出描述

格式： $int$ 类型数值

解释：所有任务全部完成需要的最短时间，用例保证存在可调度方案（不存在任务间循环依赖）

样例1

输入

输出

说明

$2$ # $2$ 个NPU卡， $3$ 个任务
$0$ # 任务 $0$ 需要NPU卡 $0$
$3$ # 任务 $0$ 持续 $3$
$-1$ # 任务 $0$ 无依赖
$0$ # 任务 $1$ 需要NPU卡 $0$
$2$ # 任务 $1$ 持续 $2$
$-1$ # 任务 $1$ 无依赖
$1$ # 任务 $2$ 需要NPU卡 $1$
$4$ # 任务 $2$ 持续 $4$
$1$ # 任务 $2$ 依赖任务 $1$

方案1：优先执行耗时长的任务（任务 $0$ 先执行）

时间 $0$ ~ $3$ NPU $0$ : 任务 $0$ （持续 $3$ ，时间 $0$ - $3$ ） NPU $1$ : 空闲（任务 $2$ 依赖任务 $1$ ，还未完成）
时间 $3$ ~ $5$ NPU $0$ : 任务 $1$ （持续 $2$ ，时间 $3$ - $5$ ） NPU $1$ : 空闲（任务 $2$ 需等待任务 $1$ ，任务 $1$ 在时间 $5$ 完成，但任务 $2$ 还未开始）
时间 $5$ ~ $9$ NPU $0$ : 空闲 NPU $1$ : 任务 $2$ （持续 $4$ ，时间 $5$ - $9$ ）

任务完成时间： 任务 $0$ : 时间 $3$ 完成任务 $1$ : 时间 $5$ 完成任务 $2$ : 时间 $9$ 完成

总时间： $9$

方案2：优先执行耗时短的任务（任务 $1$ 先执行）

时间 $0$ ~ $2$ NPU $0$ : 任务 $1$ （持续 $2$ ，时间 $0$ - $2$ ） NPU $1$ : 空闲（任务 $2$ 依赖任务 $1$ ，还未完成）
时间 $2$ ~ $6$ NPU $0$ : 任务 $0$ （持续 $3$ ，时间 $2$ - $5$ ） NPU $1$ : 任务 $2$ （持续 $4$ ，时间 $2$ - $6$ ，任务 $1$ 在时间 $2$ 已完成，满足依赖）
时间 $5$ ~ $6$ NPU $0$ : 空闲（任务 $0$ 已完成） NPU $1$ : 任务 $2$ 继续执行（时间 $5$ - $6$ ）

任务完成时间：

任务 $1$ : 时间 $2$ 完成任务 $0$ : 时间 $5$ 完成任务 $2$ : 时间 $6$ 完成

总时间： $6$

样例2

输入

输出

说明

$3$ $2$ # $3$ 个NPU卡， $2$ 个任务
$0\ 1$ # 任务 $0$ 需要NPU卡 $0$ 、卡 $1$
$4$ # 任务 $0$ 持续 $4$
$-1$ # 任务 $0$ 无依赖
$1\ 2$ # 任务 $1$ 需要NPU卡 $1$ 、卡 $2$
$5$ # 任务 $1$ 持续 $5$
$0$ # 任务 $1$ 依赖任务 $0$

调度顺序：任务 $1$ 依赖任务 $0$ ，只能先执行任务 $0$ 再执行任务 $1$ ，总耗时 $4+5=9$ ，输出 $9$

提示 $NPU$ 编号从 $0$ 开始，任务编号从 $O$ 开始

编辑器加载中…

输入

预期输出（选填）

解题思路

P5106.第3题-昇腾NPU协同调度系统

题目内容

任务属性（每个任务包含 $3$ 个维度）

调度规则

输入描述

输出描述

样例1

样例2

Status

Development

Support

About