二叉树任务调度

难度: Hard

任务调度优化是计算机性能优化的关键任务之一。在任务众多时，不同的调度策略可能会得到不同的总体执行时间，因此寻求一个最优的调度方案是非常有必要的。

通常任务之间是存在依赖关系的，即对于某个任务，你需要先完成他的前导任务（如果非空），才能开始执行该任务。我们保证任务的依赖关系是一棵二叉树，其中 root 为根任务，root.left 和 root.right 为他的两个前导任务（可能为空），root.val 为其自身的执行时间。

在一个 CPU 核执行某个任务时，我们可以在任何时刻暂停当前任务的执行，并保留当前执行进度。在下次继续执行该任务时，会从之前停留的进度开始继续执行。暂停的时间可以不是整数。

现在，系统有两个 CPU 核，即我们可以同时执行两个任务，但是同一个任务不能同时在两个核上执行。给定这颗任务树，请求出所有任务执行完毕的最小时间。

示例 1：

输入：root = [47, 74, 31]

输出：121

解释：根节点的左右节点可以并行执行31分钟，剩下的43+47分钟只能串行执行，因此总体执行时间是121分钟。

示例 2：

输入：root = [15, 21, null, 24, null, 27, 26]

输出：87

示例 3：

输入：root = [1,3,2,null,null,4,4]

输出：7.5

限制：

1 <= 节点数量 <= 1000
1 <= 单节点执行时间 <= 1000

Submission

运行时间: 54 ms

内存: 16.5 MB

# Definition for a binary tree node.
# class ceeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution():
    def minimalExecTime(self, root):
        def dfs(root):
            if root is None:
                return 0., 0.
            tc = root.val
			
            # 先递归左右子树
            a, b = dfs(root.left)
            c, d = dfs(root.right)
            
            tc = tc + a + c
            # 只考虑 a >= c 的情况，不满足就交换
            if a < c:
                a, c = c, a
                b, d = d, b
            
            if a - 2 * b <= c:
                pc = (a + c) / 2
            else:
                pc = c + b

            return tc, pc

        tc, pc = dfs(root)
        return tc - pc

Explain

这题解的方法基于深度优先搜索（DFS）来解决二叉树的任务调度问题。核心思想是考虑每个节点与其子节点的任务执行时间，以及如何利用两个CPU核心来最小化总执行时间。对于每个节点，我们首先计算其左右子树的总任务时间和最佳可能的并行执行时间。然后，根据子树返回的最优并行时间和任务时间，决定当前节点的最优执行策略。如果左子树的最大并行时间和右子树的总任务时间之差不大于右子树的最大并行时间，就可以尝试最大化并行执行。否则，将左子树的剩余部分和右子树并行。最终，返回根节点的总任务时间减去根节点的最大并行时间，得到总的最小执行时间。

时间复杂度: O(n)

空间复杂度: O(n)

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution():
    def minimalExecTime(self, root):
        def dfs(root):
            if root is None:
                return 0., 0.
            tc = root.val

            # 先递归左右子树
            a, b = dfs(root.left)
            c, d = dfs(root.right)
            
            tc = tc + a + c
            # 只考虑 a >= c 的情况，不满足就交换
            if a < c:
                a, c = c, a
                b, d = d, b
            
            # 计算最优并行执行时间
            if a - 2 * b <= c:
                pc = (a + c) / 2
            else:
                pc = c + b

            return tc, pc

        tc, pc = dfs(root)
        return tc - pc

Explore

在算法中，`a` 和 `c` 分别代表左右子树的总任务时间，而 `b` 和 `d` 代表左右子树的最优并行执行时间。检查`a >= c`的目的是为了确保`a`（左子树的总任务时间）是较大的一个，这样做的目的是简化并行时间的计算逻辑。如果左子树的任务时间较长，那么在并行执行的策略中，我们需要确保较长的任务时间能够尽可能与右子树的任务时间配合，以达到最佳的并行效率。交换`a`和`c`以及`b`和`d`的值，是为了保证计算过程中总是将较长的任务时间视为`a`，简化了后续的并行时间计算判断，使得代码逻辑更清晰和统一。

`tc` 代表当前节点及其所有子树的总任务时间，而 `pc` 代表在最佳并行调度下，可以达到的最大并行执行时间。这种返回值设计使得每次递归调用都提供了当前节点树的总任务时间和当前树结构下可能达到的最优并行时间，这样就可以基于子树的返回值来计算当前节点的最优并行执行策略。这种设计有助于从底部向上合并和计算各个节点的时间值，逐步构建出整棵树的最优时间调度方案，更加直观且容易实现。

该算法设计尽量确保两个CPU核心的充分利用通过合理的并行执行策略。算法中通过比较左右子树的总任务时间和最大并行时间，来决定如何分配任务到两个CPU核心上。特别是在并行时间计算的逻辑中，考虑了各种情况以最大化并行效率。例如，如果左子树任务时间减去两倍右子树最大并行时间仍然大于或等于右子树的总任务时间，那么可以尝试将左右子树的任务完全并行执行。然而，在极端情况下，如一个子树的任务时间远大于另一个，可能会导致一个核心的使用率低于另一个核心，但这种情况已尽可能通过算法中的策略来缩小。总的来说，算法试图通过动态调整任务分配来最小化任何核心的空闲时间。