难度: Hard
Submission
运行时间: 31 ms
内存: 16.1 MB
class Solution:
def minBuildTime(self, blocks: List[int], split: int) -> int:
def check(x: int) -> int:
if x == 0:
return False
s = 1
t = 0
i = len(blocks) - 1
while t <= x and i >= 0:
if s >= i + 1:
return True
while i >= 0 and t + split > x - blocks[i]:
s -= 1
if s < 0:
return False
i -= 1
t += split
s *= 2
if i < 0:
return True
return False
left, right = 0, 1000000
blocks.sort()
while left <= right:
mid = left + (right - left) // 2
if check(mid):
right = mid - 1
else:
left = mid + 1
return left
Explain
题解采用二分查找和贪心算法的组合。首先对blocks数组进行排序，以便使用贪心策略。定义一个辅助函数check(x)，该函数用来判断是否可以在时间x内完成所有blocks的建造。在check函数中，使用一个贪心的方法，模拟以时间x为限制条件下的工作流程。如果在时间x内可以完成建造，返回True；否则返回False。在主函数中，通过二分查找的方法，寻找满足条件的最小时间x。
时间复杂度: O(n log(max(blocks)))
空间复杂度: O(n)
class Solution:
def minBuildTime(self, blocks: List[int], split: int) -> int:
def check(x: int) -> int:
if x == 0:
return False
s = 1 # 初始化工人数量为1
t = 0 # 初始化当前耗时为0
i = len(blocks) - 1 # 从最大的block开始
while t <= x and i >= 0:
if s >= i + 1:
return True # 如果工人数足够，则直接完成
while i >= 0 and t + split > x - blocks[i]:
s -= 1 # 工人不足，需要等待
if s < 0:
return False # 工人数为负，不可能完成
i -= 1
t += split # 增加分裂时间
s *= 2 # 工人数翻倍
if i < 0:
return True # 所有block都已处理
return False
left, right = 0, 1000000 # 初始化二分查找范围
blocks.sort() # 排序blocks
while left <= right:
mid = left + (right - left) // 2 # 计算中间值
if check(mid):
right = mid - 1 # 缩小查找范围
else:
left = mid + 1 # 扩大查找范围
return left # 返回最小可能时间
Explore
从blocks数组的最大值开始处理是因为这些大的block通常需要更长的时间来完成，而且它们对于确定是否能在给定的时间内完成所有任务影响更大。处理最大的blocks首先可以更快地判断出不可能在时间限制内完成的情况，从而提高算法的效率。此外，从大到小的处理顺序可以帮助尽可能地利用现有的时间，因为大的blocks如果不能在限制时间内完成，小的blocks自然也难以在剩余时间内完成。
初始的`right`值为1000000是一个基于问题规模和实际情况的估计值。此值应足够大，以确保它覆盖所有可能的最大构建时间。这个值通常是基于对输入数据（如blocks数组中的最大值）和split时间的理解。在没有具体数据或明确的时间限制要求的情况下，选择一个大的数值如1000000，可以确保二分查找的上界覆盖所有可能的情况，但在实际应用中，这个值可能需要根据具体问题的数据范围进行调整。
检查`i >= 0 and t + split > x - blocks[i]`是为了确保在当前的时间限制x内，即使工人数翻倍后，也有足够的时间来完成当前处理的block。这一检查是为了验证在增加了分裂时间（即新的工人准备时间）后，是否还有足够的剩余时间来处理当前的block。如果处理当前block所需的时间加上分裂时间超过了总的时间限制，那么这表明在当前的时间限制内无法完成建造，因此需要调整时间限制。这一步骤是为了保证即使资源（工人数）扩充，也要满足时间上的可行性。
实际上，在给定的代码中，工人数`s`从1开始且在每次循环时都会翻倍，因此`s`不会小于0。这部分代码的描述可能是一个逻辑错误或者解释错误。正确的应该是，如果在任何时点工人数量不足以继续工作，则可以考虑返回False。即，如果在处理过程中发现需要的工人数大于当前的工人数，那么应该返回False。在代码实现中，应确保逻辑一致性和描述准确性。