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

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

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

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

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

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

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