Simplest proof of greedy correctness
Suppose an ordering of the tasks can be completed with some initial energy; assume the ordering has consecutive tasks [a1, m1] and [a2, m2] where m1 - a1 < m2 -
Suppose an ordering of the tasks can be completed with some initial energy; assume the ordering has consecutive tasks `[a1, m1]` and `[a2, m2]` where `m1 - a1 < m2 - a2`.\n\nWe claim we can reverse the order of these two tasks, and the result will still be completable with the same initial energy. Indeed, suppose energy `R` remains at the time of processing `[a1, m1]` in the original sequence. We only need to show that `R - a2 \u2265 m1`. By assumption we have `a2 < m2 - m1+ a1`; and thus,\n\n```\nR - a2 > R - (m2 - m1 + a1) = m1 + (R - a1 - m2) \n```\n\nBut `R - a1 \u2265 m2` because the original ordering can be completed. Hence `R - a2 > m1` and we can safely swap any such adjacent pair of tasks; which is equivalent to saying we can choose tasks in descending order of `mI - aI`. \u25A1
[]