Earliest Possible Day of Full Bloom

Problem

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 ith 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 ith 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.

Examples

Example 1:

1
2
3
4
5
6
7
8


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:

1
2
3
4
5
6
7
8
9


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:

1
2
3
4


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.

Solution

Method 1 – Greedy Sorting by Grow Time

Intuition

To minimize the day when all flowers bloom, plant seeds with the longest grow time first. This way, their lengthy growth can overlap with the planting of other seeds, reducing the total time.

Approach

Pair each seed’s plantTime and growTime.
Sort seeds in descending order of growTime.
Initialize curr (current day) and ans (latest bloom day) to 0.
For each seed in sorted order:

Add its plantTime to curr (accumulate planting days).
Calculate bloom day as curr + growTime.
Update ans to the maximum bloom day seen so far.

Return ans.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution {
public:
   int earliestFullBloom(vector<int>& plantTime, vector<int>& growTime) {
      int n = plantTime.size();
      vector<pair<int, int>> seeds(n);
      for (int i = 0; i < n; ++i)
        seeds[i] = {growTime[i], plantTime[i]};
      sort(seeds.rbegin(), seeds.rend());
      int curr = 0, ans = 0;
      for (auto& [g, p] : seeds) {
        curr += p;
        ans = max(ans, curr + g);
      }
      return ans;
   }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


type Solution struct{}

func (Solution) EarliestFullBloom(plantTime []int, growTime []int) int {
   n := len(plantTime)
   seeds := make([][2]int, n)
   for i := 0; i < n; i++ {
      seeds[i] = [2]int{growTime[i], plantTime[i]}
   }
   sort.Slice(seeds, func(i, j int) bool {
      return seeds[i][0] > seeds[j][0]
   })
   curr, ans := 0, 0
   for _, s := range seeds {
      curr += s[1]
      if curr+s[0] > ans {
        ans = curr + s[0]
      }
   }
   return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution {
   public int earliestFullBloom(int[] plantTime, int[] growTime) {
      int n = plantTime.length;
      int[][] seeds = new int[n][2];
      for (int i = 0; i < n; i++)
        seeds[i] = new int[]{growTime[i], plantTime[i]};
      Arrays.sort(seeds, (a, b) -> b[0] - a[0]);
      int curr = 0, ans = 0;
      for (int[] s : seeds) {
        curr += s[1];
        ans = Math.max(ans, curr + s[0]);
      }
      return ans;
   }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution {
   fun earliestFullBloom(plantTime: IntArray, growTime: IntArray): Int {
      val seeds = plantTime.indices.map { growTime[it] to plantTime[it] }
        .sortedByDescending { it.first }
      var curr = 0
      var ans = 0
      for ((g, p) in seeds) {
        curr += p
        ans = maxOf(ans, curr + g)
      }
      return ans
   }
}

1
2
3
4
5
6
7
8


class Solution:
   def earliestFullBloom(self, plantTime: list[int], growTime: list[int]) -> int:
      seeds = sorted(zip(growTime, plantTime), reverse=True)
      curr = ans = 0
      for g, p in seeds:
        curr += p
        ans = max(ans, curr + g)
      return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


impl Solution {
   pub fn earliest_full_bloom(plant_time: Vec<i32>, grow_time: Vec<i32>) -> i32 {
      let mut seeds: Vec<(i32, i32)> = grow_time.into_iter().zip(plant_time).collect();
      seeds.sort_unstable_by(|a, b| b.0.cmp(&a.0));
      let (mut curr, mut ans) = (0, 0);
      for (g, p) in seeds {
        curr += p;
        ans = ans.max(curr + g);
      }
      ans
   }
}

Complexity

Time: O(n log n) (for sorting)
Space: O(n) (for storing pairs)

Problem#

Examples#

Solution#

Method 1 – Greedy Sorting by Grow Time#

Intuition#

Approach#

Code#

Complexity#