Leetcode 1665. Minimum Initial Energy to Finish Tasks

문제

You are given an array tasks where tasks[i] = [actuali, minimumi]:

actuali is the actual amount of energy you spend to finish the ith task.
minimumi is the minimum amount of energy you require to begin the ith task.
For example, if the task is [10, 12] and your current energy is 11, you cannot start this task. However, if your current energy is 13, you can complete this task, and your energy will be 3 after finishing it.

You can finish the tasks in any order you like.

Return the minimum initial amount of energy you will need to finish all the tasks.

tasks[i] = [actual_i, minimum_i] 형태의 작업 배열 tasks가 주어집니다.

actual_i: $i$번째 작업을 완료하는 데 실제로 소비되는 에너지 양입니다.

minimum_i: $i$번째 작업을 시작하기 위해 필요한 최소 에너지 양입니다.

예를 들어, 작업이 [10, 12]일 때 현재 에너지가 11이라면 이 작업을 시작할 수 없습니다.

반면, 현재 에너지가 13이라면 작업을 완료할 수 있으며,

완료 후 남은 에너지는 $13 - 10 = 3$이 됩니다.작업은 원하는 순서대로 완료할 수 있습니다.모든 작업을 완료하기 위해 필요한 최소한의 초기 에너지 양을 반환하세요.

예시

입력: tasks = [[1,2],[2,4],[4,8]]
출력: 8

설명:
8의 에너지로 시작하여 다음과 같은 순서로 작업을 완료한다고 가정해 보겠습니다.

• 3번째 작업 [4, 8]: 시작 조건(8)을 충족하므로 수행 가능합니다. 완료 후 남은 에너지는 $8 - 4 = 4$입니다.
• 2번째 작업 [2, 4]: 시작 조건(4)을 충족하므로 수행 가능합니다. 완료 후 남은 에너지는 $4 - 2 = 2$입니다.
• 1번째 작업 [1, 2]: 시작 조건(2)을 충족하므로 수행 가능합니다. 완료 후 남은 에너지는 $2 - 1 = 1$입니다.

비록 마지막에 에너지가 남더라도, 7의 에너지로 시작하면 3번째 작업(최소 8 필요)을 수행할 수 없기 때문에 최소 에너지는 8이 됩니다.

제한

• $1 <= tasks.length <= 10^5$

• $1 <= actual​i <= minimumi <= 10^4$

• 배열의 길이가 10^5를 넘기 떄문에 O(N^2) 미만 알고리즘을 사용해야 한다.

풀이

• 겉보기엔 어려워 보일수 있는데

1. 배열 내부의 값 a에 대해 a[1] - a[0] 즉 필요한 최소양에 비해 진짜 필요한 양을 기준으로 내림차순 정렬한다.

• 즉, 실제 쓰는것보다 더 많이 필요한것들 먼저 처리한다.

2. for loop를 돌며 그때 그때 필요한 만큼 채워준다.
3. 채운 양을 전부 더해 리턴, 끝!

class Solution:
    def minimumEffort(self, tasks: List[List[int]]) -> int:
        tasks.sort(key=lambda a: a[1] - a[0], reverse=True)

        ans = 0
        node = 0

        for c, m in tasks:
            if node < m:
                val = m - node
                node += val
                ans += val

            node -= c

        return ans