Problem Description
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. Your task is to return the earliest possible day where all seeds are blooming.
Key Insights
- Each seed requires a specific number of days to be planted and a specific number of days to grow.
- The order of planting seeds affects the blooming time due to the growth times associated with each seed.
- To minimize the overall blooming time, seeds with longer growth times should be planted earlier.
- Sorting the seeds based on their growth times in descending order allows us to prioritize seeds that take longer to grow.
Space and Time Complexity
Time Complexity: O(n log n) - due to sorting the seeds based on grow times.
Space Complexity: O(n) - for storing the sorted seeds and any additional variables.
Solution
We will sort the seeds based on their growth times in descending order. By doing this, we ensure that the seeds which take longer to bloom are planted earlier, thereby minimizing overall blooming time. We will keep track of the current day and calculate the blooming day for each seed, updating the maximum blooming day as we go.