597. Earliest Full Bloom
A greenhouse has n flower seeds, and one gardener who can work on only one seed at a time. Seed i needs plant[i] full days of the gardener's attention, done in one uninterrupted stretch, and once that stretch ends the seed needs grow[i] further days on its own before it blooms. Growing needs no attention, so the gardener moves straight to another seed.
The gardener may choose the order in which seeds are planted, starting at day 0 and never idling. Return the smallest number of days after which every seed has bloomed, that is, the minimum over all orders of the largest value of (planting finish day + grow[i]). Solve it in O(n log n) time and O(n) space.
Example 1
- Input:
- plant = [2,3], grow = [4,1]
- Output:
- 6
- Explanation:
Plant the seed with grow 4 first (ends day 2, blooms day 6), then the other (ends day 5, blooms day 6), so everything has bloomed after 6 days.
Example 2
- Input:
- plant = [1,1,1], grow = [3,2,1]
- Output:
- 4
- Explanation:
Planting in order of decreasing grow time finishes at days 1, 2, 3 and blooms at days 4, 4, 4, giving 4.
Example 3
- Input:
- plant = [5], grow = [2]
- Output:
- 7
- Explanation:
With a single seed the answer is plant + grow = 7.
Constraints
1 ≤ n ≤ 100000, wheren = plant.length = grow.length1 ≤ plant[i], grow[i] ≤ 10000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,400 msC++ 600 msJava 1,200 msJavaScript 1,200 msTypeScript 1,200 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)