When the Whole Garden Blooms

Hard

You have n seeds. Each one has to be sown first; then it grows and blooms. - Sowing seed i takes sow_days[i] full days of work. Each day you work on exactly one seed; the days spent on one seed need not be consecutive, but sowing is done only once sow_days[i] days have gone into it. - Once sown, the seed grows for grow_days[i] full days, then blooms and stays in bloom for good. Work starts at the beginning of day 0 and the seeds may be sown in any order. Return the earliest day on which every seed is in bloom.

Example 1

sow_days=[2, 1, 3], grow_days=[1, 5, 2] → 7

Sow flower 1 first (day 0); it blooms on day 6. Then flower 2 (days 1–3), blooming on day 6. Then flower 0 (days 4–5), blooming on day 7. Nothing beats 7: sowing alone takes 6 days and the last flower still needs at least a day to grow.

Example 2

sow_days=[4], grow_days=[3] → 7

Sowing takes days 0–3 and growing 3 more days, so it blooms on day 7.

Example 3

sow_days=[1, 1, 1], grow_days=[2, 2, 2] → 5

Constraints

n == len(sow_days) == len(grow_days)
1 ≤ n ≤ 10⁵
1 ≤ sow_days[i], grow_days[i] ≤ 10⁴

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Sorting

Similar problems

Growing Capital Project by Project Hard Distinct Word Shorthands Hard Most Orders by Their Deadlines Hard Narrowest Range Touching Every List Hard Two Marks in Every Range Hard

Input

sow_days=[2, 1, 3], grow_days=[1, 5, 2]

Expected

Run checks the first 3 tests in your browser. Submit checks all 104 tests on the server, hidden ones included.