#2136

Earliest Possible Day of Full Bloom

specialist · 980 · lc hard +32 · verified · 71.2% accepted · 1,674 likes · top 80%

⚑ Custom Comparator Sort

Description

You have n flower seeds to plant and grow. Each seed must first be planted before it can grow and bloom. You are given two 0-indexed integer arrays plantTime and growTime, each of length n:

 - plantTime[i] is the total number of days needed to finish planting seed i. Each day you can work on only one seed, but days do not need to be consecutive. Planting is complete after plantTime[i] total work days.

 - growTime[i] is the number of days seed i takes to grow once fully planted. After its growth period ends, the flower blooms permanently.

Starting from day 0, you may plant seeds in any order.

Return the earliest day on which all flowers are simultaneously blooming.

Example 1:

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.
One optimal way is:
On day 0, plant the 0th seed. The seed grows for 2 full days and blooms on day 3.
On days 1, 2, 3, and 4, plant the 1st seed. The seed grows for 3 full days and blooms on day 8.
On days 5, 6, and 7, plant the 2nd seed. The seed grows for 1 full day and blooms on day 9.
Thus, on day 9, all the seeds are blooming.

Example 2:

Input: plantTime = [1,2,3,2], growTime = [2,1,2,1]
Output: 9
Explanation: The grayed out pots represent planting days, colored pots represent growing days, and the flower represents the day it blooms.
One optimal way is:
On day 1, plant the 0th seed. The seed grows for 2 full days and blooms on day 4.
On days 0 and 3, plant the 1st seed. The seed grows for 1 full day and blooms on day 5.
On days 2, 4, and 5, plant the 2nd seed. The seed grows for 2 full days and blooms on day 8.
On days 6 and 7, plant the 3rd seed. The seed grows for 1 full day and blooms on day 9.
Thus, on day 9, all the seeds are blooming.

Example 3:

Input: plantTime = [1], growTime = [1]
Output: 2
Explanation: On day 0, plant the 0th seed. The seed grows for 1 full day and blooms on day 2.
Thus, on day 2, all the seeds are blooming.

Code

1
2
3