1665. Minimum Initial Energy to Finish Tasks - cocoder39/coco39_LC GitHub Wiki

1665. Minimum Initial Energy to Finish Tasks

Step 1:

Proof: https://leetcode.com/problems/minimum-initial-energy-to-finish-tasks/discuss/944633/Explanation-on-why-sort-by-difference

Given 2 tasks where task1 = [a, a + c1] and task2 = [b, b + c2], where c1 < c2

• Option 1: finish [a, a + c1] then [b, b + c2]

  • since c1 < c2 => c1 < b+c2 => min total energy = a + b + c2

• Option 2: finish [b, b + c2] then [a, a + c1]

  • if c2 < a + c1 => min total energy = b + a + c1 < option 1
  • if c2 > a + c1 => min total energy = b + c2 < option 1

So always should choose option 2 to minimize total energy

Step 2: In order to easily calculate the total energy, the program will process tasks in reverse order

class Solution:
    def minimumEffort(self, tasks: List[List[int]]) -> int:
        tasks.sort(key = lambda task: task[1] - task[0])
        res = 0
        for actual, minimum in tasks:
            res = max(res + actual, minimum)
        return res