Python3 - greedy, with intuition, algorithm, and proof
Intuition\nFor the last task, we will want to minimize the waste of energy, so we take the task which has the smallest (minimum - actual). If we waste more ener
**Intuition**\nFor the last task, we will want to minimize the waste of energy, so we take the task which has the smallest (minimum - actual). If we waste more energy, we know it could be done, but it is just not optimal.\n\n**Algorithm**\nContinuing this thinking for all the remaining tasks, we know at each step, we must choose a task that minimizes the waste of energy. Hence we sort the tasks by the waste of energy from smallest to biggest.\n\nThen for each subsequent task `i`, the starting energy to finish it will be one of the 2 following cases:\n\n1. The previous energy up to task `i-1`, plus the current actual consumed energy for task `i`.\n2. The minimum starting energy of task `i`.\n\nWe will take the maximum of the two above cases in each iteration.\n\n**Proof**\nSuppose we have task0 and task1, which has the (actual, minimum) enegery to be (a0, m0) and (a1, m1), respectively. Without loss of generality, we assume m0 - a0 < m1 - a1. In our greedy approach, we will definitely choose task0 as the latter task to finish. \n\nOur greedy approach will require a starting energy of T0 = max(m0 + a1, m1). Now prove by contradiction. Suppose we will choose task1 as the latter one to finish, which achieves lower starting energy. Namely, T1 =   max(m1 + a0, m0) < T0. (\\*)\n\n(1) Because m0 - a0 < m1 - a1, we have m1 + a0 > m0 + a1. \n(2) m1 + a0 > m1 because a0 is positive.\n\nDue to (1) and (2), we have m1 + a0 > max(m0 + a1, m1) = T0. \nHence we have T1 = max(m1 + a0, m0) >= m1 + a0 > T0. But T1 > T0 contradicts (\\*). Done\n\n```python\nclass Solution:\n    def minimumEffort(self, tasks: List[List[int]]) -> int:\n        n = len(tasks)\n        t = sorted(tasks, key=lambda v:v[1]-v[0])\n        start = t[0][1]\n        for i in range(1, n):\n            start = max(start + t[i][0], t[i][1])\n        return start\n```
[]