---

1199. 建造街区的最短时间

• 标签：贪心、数组、数学、堆（优先队列）
• 难度：困难

题目链接

• 1199. 建造街区的最短时间 - 力扣

题目大意

描述：你是个城市规划工作者，手里有一系列街区需要建造。$blocks[i] = t$ 表示第 $i$ 个街区需要 $t$ 个时间单位来建造。每个街区只能由一个工人来建造。

一开始只有 $1$ 个工人。工人可以做两件事：

• 分裂：一个工人可以再召唤一个工人（工人数 $+1$），分裂花费的时间由 $split$ 给出。多个工人同时分裂时，时间花费仍然是 $split$（并行进行）。
• 建造：工人建造完一个街区后就回家了。

要求：输出建造完所有街区所需的最少时间。

说明：

• $1 \le blocks.length \le 10^3$。
• $1 \le blocks[i] \le 10^5$。
• $1 \le split \le 10^3$。

示例：

• 示例 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：哈夫曼树 + 最小堆

为什么用哈夫曼树的思想？ 每个工人相当于一棵树的叶子，分裂操作相当于创建内部节点。如果一个街区建造时间很长，我们希望它尽早被分配到工人（即尽早出现在合并中），这样它的时间可以和分裂并行进行。每次选两个最小的合并，就能保证耗时长的任务尽早被安排。

具体做法：用最小堆来维护当前所有的"任务时间"。

拆解步骤：

1. 把所有街区的建造时间放入最小堆。

2. 循环合并：只要堆里还有超过一个元素：

   • 从堆中取出两个最小的建造时间 $t_1$ 和 $t_2$
   • 合并它们：需要一个工人先分裂（花费 $split$ 时间），然后两个工人并行建造，总时间 = $split + \max(t_1, t_2)$
   • 把合并后的时间放回堆中

3. 堆中只剩一个元素时，这个值就是建造完所有街区所需的最少时间。

用人话举个例子：假设 blocks = [1, 2, 3], split = 1。

• 先取 1 和 2 合并：$1 + \max(1, 2) = 3$，堆变为 [3, 3]
• 再取 3 和 3 合并：$1 + \max(3, 3) = 4$
• 答案是 4，和题目示例一致。

思路 1：代码

import heapq

class Solution:
    def minBuildTime(self, blocks: List[int], split: int) -> int:
        # 把街区建造时间变成最小堆
        heapq.heapify(blocks)

        # 不断合并，直到只剩一个任务
        while len(blocks) > 1:
            # 取出建造时间最短的两个街区
            t1 = heapq.heappop(blocks)
            t2 = heapq.heappop(blocks)

            # 合并：先分裂工人（花费 split 时间），再并行建造
            # 总时间 = split + max(t1, t2)
            merged_time = split + max(t1, t2)

            # 把合并后的时间放回堆中
            heapq.heappush(blocks, merged_time)

        # 堆中剩下的就是最小总时间
        return blocks[0]

思路 1：复杂度分析

• 时间复杂度：$O(n \log n)$。用人话说就是：有 $n$ 个街区就需要合并 $n-1$ 次，每次合并操作（取出两个、放回一个）需要 $\log n$ 的时间。
• 空间复杂度：$O(1)$。直接在输入数组上建堆，没有使用额外的存储空间。