LC 1665. 完成所有任务的最少初始能量

https://leetcode-cn.com/problems/minimum-initial-energy-to-finish-tasks/

终于遇到一道题看上去像是贪心算法的了，但是这题最好需要证明。题解里面有个同学给了比较完整的证明，但是我这里想写写自己的证明，启发式的简化版证明吧。

我们考虑两个任务的安排情况T1(a1, m1)和T2(a2, m2)

• 如果是T1, T2这样的话，那么需要能量是 `max(m1, m2 + a1)`
• 如果是T2, T1这样的话，那么需要能量是 `max(m2, m1 + a2)`

假设第一种情况更好的话，那么就要求 `max(m1, m2+a1) < max(m2, m1+a2)`, 简化一下就要求 `max(m2+a1) < max(m1+a2)` 这样得到的结果就是 `(m2-a2) < (m1-a1)`. 所以我们应该按照 `(m-a)` 进行排序，在进行操作的时候将值大的放在前面。

操作的时候将值大的放在前面，但是在计算初始最小能量的时候则需要反推，假设 T1, T2 .. Tn, 那么反推就是

• mn + a1 + a2 + … an-1
• mn-1 + a1 + a2 + … an-2
• mn-2 + a1 + …. an-3
• ….
• m1

class Solution:
    def minimumEffort(self, tasks: List[List[int]]) -> int:
        tmp = []
        for a, m in tasks:
            tmp.append((a, m))

        def keyFn(x):
            a, m = x
            return -(m - a)

        tmp.sort(key=keyFn)
        # print(tmp)

        ans = 0
        acc = 0
        for a, m in tmp:
            ans = max(ans, acc + m)
            acc += a
        return ans