Earliest Possible Day of Full Bloom
You have n flower seeds. Every seed must be planted first before it can begin to grow, then bloom. Planting a seed takes time and so does the growth of a seed.
You are given two 0-indexed integer arrays plantTime and growTime, of length n each:
plantTime[i]is the number of full days it takes you to plant thei^thseed. Every day, you can work on planting exactly one seed. You do not have to work on planting the same seed on consecutive days, but the planting of a seed is not complete until you have workedplantTime[i]days on planting it in total.growTime[i]is the number of full days it takes thei^thseed to grow after being completely planted. After the last day of its growth, the flower blooms and stays bloomed forever.
From the beginning of day 0, you can plant the seeds in any order.
Return the earliest possible day where all seeds are blooming.
Example 1
Input
plantTime = [1,4,3], growTime = [2,3,1]Output
9One optimal schedule makes the 0^th seed bloom on day 3, the 1^st seed bloom on day 8, and the 2^nd seed bloom on day 9, so all seeds are blooming on day 9.
Example 2
Input
plantTime = [1,2,3,2], growTime = [2,1,2,1]Output
9One optimal schedule makes the seeds bloom no later than day 9, so on day 9 all the seeds are blooming.
Constraints
- n == plantTime.length == growTime.length
- 1 <= n <= 10^5
- 1 <= plantTime[i], growTime[i] <= 10^4