Leetcode 1199 建造街区的最短时间（贪心算法及证明）

题目链接

这道题的最佳解法是使用小根堆的贪心方法，但其正确性并不是显而易见的。这里，我们结合具体场景来对贪心方法的正确性进行分析。

一个街区的情形

不需要分裂工人，直接让他去建造街区就好了。花费时间
$blocks[0]$

两个街区的情形

我们必须先把当前的工人分裂为两个工人，然后让他们分别去建造街区。花费时间

$split+\max(blocks[0], blocks[1])$

N个街区的情形

如果我们继续按照这样的正向思维来分析，最后得到的可能就是一个DFS的方法。因为我们每一步都需要去抉择将几个工人进行分裂，而这一抉择的优劣并不是显然的，因此好的剪枝策略不易找到。

我们不妨换一个角度来理解，如果我们不是分裂工人，而是合并街区呢？上面两个街区的情形中，分裂工人的操作，实际上就等价于把这两个街区合并为了一个建造时间为
$split+\max(blocks[0], blocks[1])$
的新街区。

考虑对 $N$ 个街区进行合并。我们可以看到，选择任意两个街区 $i$ 和 $j$ 进行合并后，得到的“新”街区建造时间为：
$split+\max(blocks[i],blocks[j])$

Huffman Tree的启示

看到这里，不知道大家有没有想到经典的Huffman Tree？在Huffman Tree中，两个节点合并后得到的新节点为 $a[i]+a[j]$ 。为了让数值大的节点尽可能少参与到合并中，我们总是优先挑选两个最小的节点来进行合并。

本题中也是一样，为了让耗时长的街区尽可能少参与到合并中，我们总是优先挑选两个耗时最小的街区（这里的街区，可能是由之前操作合并得到的）进行合并。所以我们可以维护一个小根堆，每次取最上方两个街区进行合并，然后将合并得到的新街区重新加入堆中。

正确性的证明

如何严格证明这一贪心策略的正确性呢？我们可以参考Huffman Tree的证明过程，使用归纳法来进行证明。

问题重述

我们首先把对问题进行重述。根据前面的分析，将分裂工人转化为合并街区后，这一问题就可以重述为：

设有 $n(n\geq 2)个数$ ，合并任意两个数 $x$ 和 $y$ 后得到一个新的数 $s+max(x,y)$ ，其中 $s>0$ 且与 $x,y$ 无关。那么，合并 $n-1$ 次后最终得到的数的最小值是多少？

而我们解决这一问题的策略，即是上述的贪心策略：每次选取两个最小的数进行合并，直到只剩下一个数为止。

引理及证明

在证明贪心策略的正确性之前，我们首先需要证明一个引理。

引理将合并过程表示为一棵节点的度为0或2的二叉树，其叶子节点为初始的数且至少有两个叶节点，父节点的值为 $s+max(x,y)$ ，其中 $x,y$ 为其两个子节点的值。假设 $n(n\geq 2)$ 个数中最小的两个数为 $x_1,x_2(x_1\leq x_2)$ ，则在最优合并对应的二叉树中， $x_1,x_2$ 对应的叶节点一定具有最大的深度，且为兄弟节点。

引理的证明

假设存在一个叶节点 $x_3$ ，其深度 $d_3$ 大于 $x_1$ 的深度 $d_1$ ，且 $x_3\geq x_1$ 。假设 $x_3$ 的深度为 $d_1$ 的祖先节点为 $y$ ，则 $y\geq x_3 + (d_3 - d_1)s>x_3\geq x_1$ 。考虑所有深度为 $d_1$ 的节点的最大值 $M$ ，可以得到
$M=\max(x_{d_1})=\max(y, x_1, ...)=\max(y, y, ...)$
尝试交换 $x_1$ 和 $x_3$ 。交换后 $y'\leq y$ ，
$M'=\max(y', x_3, ...)\leq\max(y, y, ...)=M$
由 $M'\leq M$ 可知，交换后二叉树的根节点 $R'\leq R$ 。因此，我们总可以通过若干次交换，使得 $x_1$ 具有最大深度，并且根节点的值不大于原本根节点的值。
由于二叉树的节点度不能为1，所以深度最深的叶节点至少有两个。因此，我们可以再通过若干次交换，使得 $x_2$ 具有最大深度，并且根节点的值不大于原本根节点的值。由于 $x_2$ 的深度不能超过 $x_1$ 的深度，所以此时它们的深度一定相等。

若二叉树深度最深的一层只有两个叶节点，它们必定为 $x_1$ 和 $x_2$ 且为兄弟。
假设在二叉树深度最深的一层还有其他叶节点，则由节点的度为0或2可知，至少还有两个叶节点 $x_3,x_4$ ，且满足 $x_1\leq x_2\leq x_3,x_1\leq x_2\leq x_4$ 。若 $x_1和x_2$ 不为兄弟节点，不妨假设 $x_1$ 和 $x_3$ 为兄弟节点， $x_2和x_4$ 为兄弟节点。则 $x_1$ 和 $x_3$ 的父节点 $y=s+x_3$ ， $x_2$ 和 $x_4$ 的父节点 $z=s+x_4$ 。考虑倒数第二层的所有节点的最大值 $M$ ，可以得到
$M=\max(y,z,...)$
若将 $x_2$ 和 $x_3$ 交换，则 $y'=s+x_2\leq y,z'=s+x_4=z$ ，从而
$M'=\max(y',z',...)\leq\max(y,z,...)=M$
因此这一交换可以得到更优的合并方案。从而， $x_1$ 和 $x_2$ 一定为兄弟节点。

数学归纳

归纳基础 在 $n=2$ 时，使用贪心策略可以得到最优合并。
归纳步骤 假设 $n=k(k\geq 2)$ 时，使用贪心策略可以得到最优合并。我们需要证明：在 $n=k+1$ 时，使用贪心策略可以得到最优合并。

归纳基础的证明 由前面对两个街区情形的分析可知，归纳基础成立。
归纳步骤的证明

不妨假设 $x_1,x_2(x_1\leq x_2)$ 是 $k+1$ 个数中最小的两个数。根据贪心策略，我们将它们合并，得到一个新的数 $x'=s+\max(x_1,x_2)$ 。
将 $x'$ 和剩余 $k-1$ 个数组合在一起，由归纳假设可知，使用贪心策略可以得到这 $k$ 个数的最优合并，假设其对应的二叉树表示为T，根节点的值为 $R_T$ ，则使用贪心策略合并 $k+1$ 个数的代价也为 $R_T$ 。
我们将T中 $s+max(x_1,x_2)$ 对应的叶节点拆分出两个新的叶节点 $x_1$ 和 $x_2$ ，可以得到一棵新的二叉树T'，根节点的值为 $R_{T'}=R_T$ 。
假设存在一个比贪心策略得到的二叉树更优的合并二叉树S，则其根节点 $R_S<R_T$ ，由引理可知， $x_1$ 和 $x_2$ 一定具有最大深度，且为兄弟节点，因此我们可以把 $x_1$ 和 $x_2$ 合并得到 $x'=s+\max(x_1,x_2)$ ，这样就得到了一个具有 $k$ 个叶节点的新二叉树S'，其对应了 $x'$ 和剩余 $k-1$ 个数的一种合并方式，且其根节点 $R_{S'}=R_S<R_T$ 。这与我们的归纳假设，也即T是 $k$ 个数的最优合并，相矛盾。因此假设不成立，贪心策略得到合并 $k+1$ 个数的方法是最优合并。

参考资料

参考代码（C++）

class Solution {
public:
    int minBuildTime(vector<int>& blocks, int split) {
        priority_queue<int,vector<int>,greater<>> pq;
        
        for (int block : blocks)
            pq.push(block);
        
        while (pq.size() > 1){
            int smallest = pq.top();
            pq.pop();
            int second_smallest = pq.top();
            pq.pop();
            pq.push(split + second_smallest);
        }
        
        return pq.top();
    }
};

Leetcode 1199 建造街区的最短时间（贪心算法及证明）