C++ ] leetCode 2136 - Earliest Possible Day of Full Bloom

 

 

 

리트코드 2136 문제

 

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: 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:

• 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:

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

 

 

Constraints:

• n == plantTime.length == growTime.length
• 1 <= n <= 105
• 1 <= plantTime[i], growTime[i] <= 104

 

 

두번째 예시는 좀 인위적으로 복잡하게 그려놨는데 그냥 주어진 인덱스 순서대로 심어도 모든 꽃이 피는 데 9일이 걸린다.

 

첫번째와 두번째 예시를 보면 정답은 plantTime의 총 합 + 마지막으로 심은 꽃의 growTime 이다. 하지만 이건 모두 운좋게도 마지막으로 심은 꽃이 피기전에 앞전에 심은 꽃이 모두 폈기 때문에 가능한 일이다.

 

예를들어 다음과 같은 경우를 생각해보자. 인덱스의 반대 순서로 심어야 마지막 꽃이 피는 날을 앞당길 수 있다.

plantTime = [1, 1], growTime = [1, 10]

 

growTime이 특별히 오래 걸리는 꽃이 있다고 가정했을 때 최적의 방법을 찾기 위해 다음의 규칙을 세울 수 있다.

 

1. 성장시간이 오래 걸리는 꽃부터 먼저 심는다.

2. 가장 늦게 피는 꽃을 찾아낸다. 꽃이 피는 날은 해당 꽃을 심은 날 + 성장에 필요한 날이다.

 

 

먼저 growTime이 큰 순서대로 정렬된 idx 벡터를 구하고 해당 idx 순으로 꽃이 피는 날(plantTime 누적합 + growTime)을 검사하여 max 값을 찾아 리턴한다.

 

 

class Solution {
public:
    int earliestFullBloom(vector<int>& plantTime, vector<int>& growTime) {
        int totalTime = 0;
        int took = 0;
        vector<int> idx(plantTime);
        for(int i = 0; i < plantTime.size(); i++) {
            idx[i] = i;
        }

        sort(idx.begin(),idx.end(), [&](int a, int b) {
            return growTime[a] > growTime[b];
        });

        for(int i = 0; i < plantTime.size(); i++) {
            took += plantTime[idx[i]];
            int temp = took + growTime[idx[i]];
            totalTime = temp > totalTime ? temp : totalTime;
        }

        return totalTime;
    }
};