[Leetcode] 2136. Earliest Possible Day of Full Bloom

문제

 

https://leetcode.com/problems/earliest-possible-day-of-full-bloom/

Earliest Possible Day of Full Bloom - LeetCode

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.

 

Example 1:

Input	Output
plantTime = [1,4,3], growTime = [2,3,1]	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.

 

 

문제풀이 코드

class Solution:
    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:
        min_grow = 0
        result = 0
        for plant, grow in reversed(sorted(zip(plantTime, growTime), key=lambda x:x[1])):
            result = max(result, min_grow + plant + grow)
            min_grow += plant
        return result

 

 

탐욕 알고리즘

1. 모든 꽃을 심기위해서는 최소 plantTime의 합이 필요하기 때문에, growTime이 이 문제의 key가 된다

2. growTime 큰 순서대로 씨앗이 심어지면 가장 최소시간으로 모든 꽃을 피울 수 있게된다.

3. min_grow는 현재 심어진 씨앗의 최소 길이로 min_grow 이후부터 씨앗을 심을 수 있다

4. plantTime과 growTime을 하나의 배열로 합친다음 growTime이 큰 순서대로 정렬한다

5. min_grow + 씨앗 심는 시간 + 꽃이 피는 시간을 계산하여 result를 계속 변경해준다.

6. 씨앗을 심었으면 min_grow는 현재 씨앗을 심은 시간을 더해준다

7. 반복문이 종료되면 result에는 꽃을 피우는 최단시간이 들어있기 때문에 그대로 반환한다