题目大意：
建造街区的最短时间
你是个城市规划工作者，手里负责管辖一系列的街区。在这个街区列表中 blocks[i] = t 意味着第 i 个街区需要 t 个单位的时间来建造。
由于一个街区只能由一个工人来完成建造。
所以，一个工人要么需要再召唤一个工人（工人数增加 1）；要么建造完一个街区后回家。这两个决定都需要花费一定的时间。
一个工人再召唤一个工人所花费的时间由整数 split 给出。
注意：如果两个工人同时召唤别的工人，那么他们的行为是并行的，所以时间花费仍然是 split。
最开始的时候只有 一个 工人，请你最后输出建造完所有街区所需要的最少时间。
示例 1：
输入：blocks = [1], split = 1 输出：1 解释：我们使用 1 个工人在 1 个时间单位内来建完 1 个街区。
示例 2：
输入：blocks = [1,2], split = 5 输出：7 解释：我们用 5 个时间单位将这个工人分裂为 2 个工人， 然后指派每个工人分别去建造街区， 从而时间花费为 5 + max(1, 2) = 7
示例 3：
输入：blocks = [1,2,3], split = 1 输出：4 解释：将 1 个工人分裂为 2 个工人， 然后指派第一个工人去建造最后一个街区， 并将第二个工人分裂为 2 个工人。 然后，用这两个未分派的工人分别去建造前两个街区。 时间花费为 1 + max(3, 1 + max(1, 2)) = 4
提示：
1 <= blocks.length <= 10001 <= blocks[i] <= 10^51 <= split <= 100
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1199
解题思路分析：
这是一道难题，网上大部分文章都在讲使用哈夫曼算法来解题，但是为什么哈夫曼算法适用于本题，我并没有找到很明确的解释。其实我对哈夫曼的理解也很肤浅，这里就试着分析一下，如果还是不能理解，可以跳过这个部分，看我下面使用动态规划解法的思路。
具体的哈夫曼算法这里就不再详述了，对于本题，你可以将所有街区的工作理解成为n个节点，目的是将其组成一个二叉树。开始时，每个节点都可以看做是一棵独立的树，每棵树只有一个节点。然后在这n个树中找到2个根节点最小的进行合并，合并后，原先2个根节点变为2个子节点，他们的根节点是其最大值加上split。合并后，再在所有根节点中找到2个最小的进行合并，重复以上步骤，直到只剩下一棵树为止，当前树的根节点即为本题的返回值。
解题过程不难理解，但是难于理解的点在于如何证明这个思路。首先看为什么每次要找到2个最小值进行合并，合并操作实际上相当于用2个工人去同时完成2个任务，找最小值合并的原因有2：
- 由于开始时还没有其他任务在进行，尽量找到时间短的任务。将相对花时间的任务放到后面，去和其他任务并行执行相对效率较高。（此处为贪心）
- 合并2个最小值，也就是合并2个时间长度最接近的任务，这样他们同时执行的时间差最小，也就是不会浪费太多时间。（此处也为贪心）
合并后，他们的根节点变为2个子节点（原根节点）最大值加上split，这个不难理解，由于开始只有1个工人，他必须先召唤另一人后，2人才能同时开始工作。因此新生成的根节点代表，召唤1个工人的时间（split），加上2人同时开始工作并且2个任务都完成的时间（两个任务时间最大值）。
接下来是重点，由于任务（建造或者召唤都算是任务）是可以同时进行的，在第一个人开始召唤第二个人，到2个人干完工作这段时间内，其他工人是可以同时执行其他任务的！这里可能会有一个疑问，前2个人已经干完工作回家休息，哪来的其他工人？其实我们在合并前两个节点时，忽略了一种情况，即当第一个人执行召唤后，到2个人同时开始工作前这个时间段，他们还是可以继续召唤其他人的，这个召唤时间我们没有计算到根节点中，但并不意味着他们没做出召唤操作。没被计算的召唤时间我们可以累加到第3个工人与其他最小根节点合并后的根节点中，这并不影响总时间。因此整个过程其实就是在找哪些任务与哪些任务同时进行可以最优的节省时间。（这里然我想起来小学学过的一篇华罗庚的文章：统筹方法）
看下实现代码：代码很简单就不写注释了。如果还是没理解也不要紧，下面有常规动态规划解法的讲解。
public int minBuildTime(int[] blocks, int split) {
PriorityQueue<Integer> pq = new PriorityQueue();
for(int b : blocks) pq.offer(b);
while(pq.size() > 1){
int node1 = pq.poll();
int node2 = pq.poll();
pq.offer(node2 + split);
}
return pq.poll();
}本解法执行时间为8ms。
Runtime: 8 ms, faster than 99.11% of Java online submissions for Minimum Time to Build Blocks.
Memory Usage: 38.9 MB, less than 100.00% of Java online submissions for Minimum Time to Build Blocks.
解法二：动态规划
原先感觉动态规划DP的思路很难理解，做了这道题之后才发现，DP原来真香。。。
其实动态规划就是递归加记忆数组，本人比较喜欢使用递归思路，简单粗暴，这里也用递归来解题。
我们想象几种情况：
- 如果工人数大于等于还没完成的任务（建造街区）数，那么他们可以同时开工，所需时间为所有任务中所需时间的最大值。
- 如果当前只有1个工人，那么他不能建造，只能召唤（除非第一种情况）。
- 如果当前存在多个工人，那么他们可以同时召唤新的工人。因为召唤是同时进行，所以所需时间为split，召唤后，工人数翻倍，递归到子问题求解（res=split+递归结果）。
- 如果当前存在多个工人，可以让其中1个人来建造，与此同时，剩下的人做其他建造或者召唤工作（剩下的人递归到子问题，工人数减1，任务数减1）。（res=max(block[i], 递归结果)）。这里可能会有疑问，为什么没有列举2个人，3个人。。。n个人建造的情况，因为递归到子问题时可以涵盖这些可能。
- 3和4的最小值为当前如何分配工作的最优解。
看下实现代码：
int[][] memo; // 记忆数组
public int minBuildTime(int[] blocks, int split) {
Arrays.sort(blocks); // 排序任务
// 初始化记忆数组
memo=new int[blocks.length+1][blocks.length+1];
// 递归求解
return help(blocks,split,1,blocks.length-1);
}
int help(int[] blocks,int split,int worker,int index){
// 如果工人数大于等于任务数，直接返回时间最长的任务时间
if(worker>=index+1) return blocks[index];
// 如果记忆数组存在解，直接返回
if(memo[worker][index]>0){
return memo[worker][index];
}
// 所有人同时执行召唤。
int doSplit=split+help(blocks,split,worker*2,index);
// 如果当前只有1个工人，只能召唤，返回doSplit
if(worker==1) return doSplit;
// 让1个人建造，同时其他人递归到子问题。
int doBuild=Math.max(blocks[index], help(blocks,split,worker-1,index-1));
// 召唤或建造的最小值为当前最优解
int res=Math.min(doSplit, doBuild);
// 存入记忆数组
memo[worker][index]=res;
return res;
}本解法执行时间为142ms。
Runtime: 142 ms, faster than 8.93% of Java online submissions for Minimum Time to Build Blocks.
Memory Usage: 52.5 MB, less than 100.00% of Java online submissions for Minimum Time to Build Blocks.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1199-minimum-time-to-build-blocks-解题思路分析/
Pingback引用通告： LEETCODE 1167. Minimum Cost to Connect Sticks 解题思路分析 - LEETCODE从零刷LEETCODE从零刷