Earliest Possible Day of Full Bloom — LeetCode 2136 Python Solution

The problem

You have n flower seeds. Every seed must be planted first before it can begin to grow, then bloom.

Example

Input

plantTime = [1,4,3], growTime = [2,3,1]

Output

9

Explanation

The grayed out pots represent planting days, colored pots represent growing days, and the flower represents the day it blooms.

Python solution

class Solution:
    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:
        ans = t = 0
        for pt, gt in sorted(zip(plantTime, growTime), key=lambda x: -x[1]):
            t += pt
            ans = max(ans, t + gt)
        return ans

Complexity

Pattern: Greedy

Take the locally best option every time — when you can prove that never costs you later. LeetCode 2136. Earliest Possible Day of Full Bloom is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Greedy.

The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.

Related problems