5091. 建造街区的最短时间

[JalanJiang]

• 原题链接：5091. 建造街区的最短时间
• 题解链接：http://jalan.space/leetcode-notebook/#/biweekly/?id=_5091-%e5%bb%ba%e9%80%a0%e8%a1%97%e5%8c%ba%e7%9a%84%e6%9c%80%e7%9f%ad%e6%97%b6%e9%97%b4

---

• 输出题解
• 时间复杂度
• 是否最优解

[JalanJiang]

一个工人只能使用一次，所以如果有 N 个街区，那么必须召唤出 N 个工人。

1. 将 blocks 转为堆结构
2. 每次取出堆中最小的两个元素 b1 和 b2
3. 计算 split + max(b1, b2)，表示复制一个工人的耗时 + 并行修两个街区的最大耗时，并加入堆

借用 Python heapq 模块完成堆排序功能：

• heapq.heapify(blocks)：将数组转为堆结构
• heapq.heappop(blocks)：弹出最小元素
• heapq.heappush(blocks, tmp)：加入新元素

import heapq

class Solution:
    def minBuildTime(self, blocks: List[int], split: int) -> int:
        heapq.heapify(blocks)
        
        while len(blocks) > 1:
            # 弹出最小的两个任务
            b1 = heapq.heappop(blocks)
            b2 = heapq.heappop(blocks)
            # N 个街区必须召唤 N 个工人
            heapq.heappush(blocks, split + max(b1, b2))
        
        return blocks[0]