Descriptio Link to heading

2136. Earliest Possible Day of Full Bloom (Hard) Link to heading

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 the iᵗʰ seed. 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 worked plantTime[i] days on planting it in total.
• growTime[i] is the number of full days it takes the iᵗʰ seed 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: 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 0ᵗʰ seed. The seed grows for 2 full days and blooms on day 3.
On days 1, 2, 3, and 4, plant the 1ˢᵗ seed. The seed grows for 3 full days and blooms on day 8.
On days 5, 6, and 7, plant the 2ⁿᵈ 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 0ᵗʰ seed. The seed grows for 2 full days and blooms on day 4.
On days 0 and 3, plant the 1ˢᵗ seed. The seed grows for 1 full day and blooms on day 5.
On days 2, 4, and 5, plant the 2ⁿᵈ seed. The seed grows for 2 full days and blooms on day 8.
On days 6 and 7, plant the 3ʳᵈ 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 0ᵗʰ seed. The seed grows for 1 full day and blooms on day 2.
Thus, on day 2, all the seeds are blooming.

Constraints:

• n == plantTime.length == growTime.length
• 1 <= n <= 10⁵
• 1 <= plantTime[i], growTime[i] <= 10⁴

Solution Link to heading

To commence, let us establish that cross-seeding does not yield a more optimal timeframe:

Let us assume two seeds, denoted as $a$ and $b$. Without cross-seeding, we proceed by either planting $a$ first and then $b," or vice versa. This is due to the fact that when cross-seeding, the completion time for the first seed is delayed, while the planting time for the second seed remains unchanged. Hence, it is implausible for this practice to result in a more favorable timeframe. This rationale extends to scenarios involving multiple seeds.

Furthermore, let us substantiate the necessity of prioritizing the seed with the maximum $growtime.$ This is because the total planting time remains constant. Consequently, at a minimum, it requires $totalplanttime + growtime_x$ time, where $x$ represents the last planted seed. Thus, for the final seed planted, a smaller $growtime$ is more favorable. By tracing this reasoning backwards, it becomes evident that $growtime$ should systematically decrease in a sequential fashion.

Code Link to heading

class Solution {
  public:
    int earliestFullBloom(vector<int> &plantTime, vector<int> &growTime) {
        int time = accumulate(plantTime.begin(), plantTime.end(), 0);
        int cur = 0;
        int n = plantTime.size();
        vector<int> ids(n);
        for (int i = 0; i < n; ++i) {
            ids[i] = i;
        }
        auto cmp = [&growTime](int i, int j) {
            return growTime[i] > growTime[j];
        };
        sort(ids.begin(), ids.end(), cmp);
        for (int i = 0; i < n; ++i) {
            int idx = ids[i];
            cur += plantTime[idx];
            time = max(time, cur + growTime[idx]);
        }
        return time;
    }
};