Earliest Possible Day of Full Bloom

Earliest Possible Day of Full Bloom

What is this problem about?

The Earliest Possible Day of Full Bloom interview question presents a gardening challenge. You have n flower seeds. For each seed, you know the plantTime (how long it takes to plant it) and the growTime (how long it takes to grow after planting). You can only plant one seed at a time, but multiple seeds can grow simultaneously. You need to find the minimum possible time until all flowers have bloomed.

Why is this asked in interviews?

This is a high-level optimization problem asked by companies like Visa and eBay. It tests a candidate's ability to identify and prove a greedy interview pattern. The core difficulty is determining the optimal order of planting. It requires logical reasoning to see that flowers with the longest growth time should be planted as early as possible to minimize the total wait time.

Algorithmic pattern used

This problem is solved using a Greedy strategy with Sorting.

1. Sort the seeds in descending order of their growTime.
2. Maintain a running sum of currentPlantTime.
3. For each seed, the bloom time is currentPlantTime + plantTime + growTime.
4. The total time needed is the maximum bloom time across all seeds. Since all seeds must be planted eventually, the planting time is fixed. The only variable we can control is the growth overlap, which is maximized by starting the longest growth processes first.

Example explanation

Seeds:

• Seed A: plant 1, grow 4
• Seed B: plant 2, grow 2

1. If we plant A then B:
   • Day 1: Plant A. (A starts growing at end of day 1).
   • Day 2-3: Plant B. (B starts growing at end of day 3).
   • A blooms at: 1 + 4 = 5.
   • B blooms at: 1 + 2 + 2 = 5.
   • Result: 5.
2. If we plant B then A:
   • Day 1-2: Plant B. (B starts growing at end of day 2).
   • Day 3: Plant A. (A starts growing at end of day 3).
   • B blooms at: 2 + 2 = 4.
   • A blooms at: 2 + 1 + 4 = 7.
   • Result: 7. Sorting by growth time (A then B) gave the minimum time (5).

Common mistakes candidates make

• Sorting by Plant Time: Incorrectly assuming that planting fast-growing seeds first is better.
• Sorting by Total Time: Thinking that plantTime + growTime is the sorting key.
• Complexity: Trying to use dynamic programming or permutations, which are O(2^N) or O(N!) and completely unnecessary.

Interview preparation tip

When you have a set of tasks where one part is sequential (planting) and another is parallel (growing), always try to "schedule" the longest parallel tasks first. This is a common pattern in scheduling and resource management problems.