LeetCode-2136 全部开花的最早一天

LeetCode-2136 全部开花的最早一天 #

Solution 1 #

首先, 种完一枚种子再去种别的是最优的. 其次, 这个问题可以抽象成: 给定长度为 $n$ 的数组 $a, b$ , $p$ 为要寻找的下标重排列, 求解优化问题: $$ \min_{p}\max_{0\leq k < n} \sum_{0\leq i\leq k}a[p_i] + b[p_k] $$ 现在考虑相邻的两个种子 (以 $(a_1, b_1), (a_2, b_2), b_1 > b_2$ 为例) 什么时候该交换. 因为 $$ \max(a_2+ b_2, a_1 + a_2 + b_2) \geq a_1 + a_2 + b_1 \geq a_1 + a_2 + b_2 \geq \max(a_1 + b_1, a_1 + a_2 + b_2) $$ 所以保持 $b$ 递减即可. 代码如下:

class Solution:
    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:
        ans = res = 0
        for g, p in sorted(zip(growTime, plantTime), reverse=True):
            res += p
            ans = max(ans, res + g)
        return ans