题目描述
任务调度优化是计算机性能优化的关键任务之一。在任务众多时,不同的调度策略可能会得到不同的总体执行时间,因此寻求一个最优的调度方案是非常有必要的。
通常任务之间是存在依赖关系的,即对于某个任务,你需要先完成他的前导任务(如果非空),才能开始执行该任务。我们保证任务的依赖关系是一棵二叉树,其中 root
为根任务,root.left
和 root.right
为它的两个前导任务(可能为空),root.val
为其自身的执行时间。
在一个 CPU 核执行某个任务时,我们可以在任何时刻暂停当前任务的执行,并保留当前执行进度。在下次继续执行该任务时,会从之前停留的进度开始继续执行。暂停的时间可以不是整数。
现在,系统有两个 CPU 核,即我们可以同时执行两个任务,但是同一个任务不能同时在两个核上执行。给定这颗任务树,请求出所有任务执行完毕的最小时间。
样例
输入:root = [47, 74, 31]
输出:121
解释:
根节点的左右节点可以并行执行31分钟,剩下的43+47分钟只能串行执行。
因此总体执行时间是121分钟。
输入:root = [15, 21, null, 24, null, 27, 26]
输出:87
输入:root = [1,3,2,null,null,4,4]
输出:7.5
限制
1 <= 节点数量 <= 1000
1 <= 单节点执行时间 <= 1000
算法
(递归遍历,贪心) $O(n)$
- 定义递归函数,返回两个值,分别是完成以 $rt$ 为根的子树所需要的最优并行时间 $p$ 和串行时间 $s$。
- 如果 $rt$ 为空,返回 $(0, 0)$。
- 递归左右子节点,返回 $(l_p, l_s)$ 以及 $(r_p, r_s)$。不妨假设 $l_s \le r_s$,不满足则交换左右子树。
- 如果 $l_s + 2l_p \ge r_s$ 则可以拿出左子树的并行时间 $t$,让 $l_s + 2t = r_s$,这样会提高并行度,使得左右子树可以完美利用两个 CPU 并行执行。最终,$p = r_p + l_p - (r_s - l_s) / 2 + r_s$ 和 $s = rt.val$。
- 如果 $l_s + 2l_p < r_s$,则说明无论如何完成左右子树都有一个 CPU 最终闲置,此时为了最大化并行度,让一个 CPU 跑左子树,另一个 CPU 跑右子树。最终,$p = r_p + l_s + 2l_p$ 和 $s = r_s - (l_s + 2l_p) + rt.val$。
时间复杂度
- 每个节点仅遍历一次,故总时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(h)$ 的额外空间存储递归的系统栈。其中 $h$ 为树的最大高度。
C++ 代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
private:
pair<double, double> solve(TreeNode* rt) {
if (!rt) return make_pair(0, 0);
auto l = solve(rt->left);
auto r = solve(rt->right);
if (l.second > r.second) swap(l, r);
double lp = l.first, ls = l.second;
double rp = r.first, rs = r.second;
if (ls + 2 * lp >= rs)
return make_pair(rp + lp - (rs - ls) / 2 + rs, rt->val);
return make_pair(rp + ls + 2 * lp, rs - (ls + 2 * lp) + rt->val);
}
public:
double minimalExecTime(TreeNode* root) {
auto ans = solve(root);
return ans.first + ans.second;
}
};