[Python] Greedy solution with intuition and proof
The code to the greedy approach is relatively straightforward. However what makes it hard is actually proving that the greedy approach is correct.\n\nIntuition:
The code to the greedy approach is relatively straightforward. However what makes it hard is actually proving that the greedy approach is correct.\n\nIntuition:\nEach time we process a task, we\'ll have some energy left over that we can carry forward onto the next task. Ideally we\'d then want to carry as much as possible so on the next task, as little as possible energy is required.\n\nProof:\nWe have our greedy solution `G` that orders tasks in descending order of `minimum`<sub>i</sub>- `actual`<sub>i</sub>. That is for all `i`, `minimum`<sub>i</sub>- `actual`<sub>i</sub> >= `minimum`<sub>i+1</sub>- `actual`<sub>i+1</sub>. Let\'s say someone comes along with some competing solution `M` *different* from `G`. There then must exist a pair of "inversions", [`minimum`<sub>i</sub>, `actual`<sub>i</sub>] and  [`minimum`<sub>i+1</sub>, `actual`<sub>i+1</sub>] such that `minimum`<sub>i</sub>- `actual`<sub>i</sub> <= `minimum`<sub>i+1</sub>- `actual`<sub>i+1</sub>. (If there are no such inversions, then `G` is the same as `M` and there\'s nothing to prove)\n\nTo save some typing, let\'s call the inverted pair of tasks in the order `[x, x + d0]` , `[y, y + d1]` found in `M` whereas we have the opposite, greedy, order `[y, y + d1]`, `[x, x + d0]` found in in `G`. Here `d1 >= d0`, the reason for the inversion.\n\nTo process `[x, x + d0]` , `[y, y + d1]` in `M`, we\'ll need some amount of energy, let\'s call it `E`<sub>m</sub>. It must be true that: `E`<sub>m</sub> `>= x + d0` *and* `E`<sub>m</sub> `- x >= y + d1`. Why? Because we\'ll need at least `x + d0` to begin processing the first task and after having processed the task, we would have spent `x` amount of energy and would now require an additional `y + d1` amount to begin processing the second task. It then follows that `E`<sub>m</sub> `>= x + d0` *and* `E`<sub>m</sub>` >= x + y + d1` which means `E`<sub>m</sub> `>= max(x + d0, x + y + d1)`. But since `d1 >= d0`, `x + y + d1 >= x + d0` so actually `E`<sub>m</sub>`= x + y + d1`.\n\nSimilarly to process `[y, y + d1]`, `[x, x + d0]` , in `G`, we\'ll need the amount of energy we\'ll call `E`<sub>g</sub>. By the same logic, we have `E`<sub>g</sub> `>= max(y + d1, x + y + d0)`. We can\'t reduce this further like we did with `E`<sub>m</sub>.\n\nWhew! Okay almost there! We now want to show that in all cases, `E`<sub>m</sub>` >=  E`<sub>g</sub>. That is `M` is not as energy-efficient as `G` at this point.\nCase 1: if `y + d1 >= x + y + d0`, then `E`<sub>g</sub> `= y + d1`. But notice `E`<sub>m</sub>`= x + y + d1` so `E`<sub>m</sub> >= `E`<sub>g</sub>.\nCase 2: If ` x + y + d0 >= y + d1`, then `E`<sub>g</sub> `= x + y + d0`. Since `d1 >= d0`, we have `x + y + d1 >=  x + y + d0`. But that\'s just `E`<sub>m</sub> >= `E`<sub>g</sub>.\nSo we\'ve now shown given any solution `M` different from `G`, wherever we find some inversion where its task ordering differs from that in `G`, the energy required at that point will be higher than that in `G`. It then follows we can simply correct each such inversion in `M` to get a smaller required energy and when all inversions are fixed, it will converge to the greedy, optimal solution.\n\n\n```\nclass Solution:\n    def minimumEffort(self, tasks: List[List[int]]) -> int:\n        # We want to go through tasks in descending order of energy we could carry\n        # over to the next task\n        tasks.sort(key=lambda x:-(x[1] - x[0]))\n        \n        curr_energy = 0\n        borrowed = 0\n        for i in range(len(tasks)):\n            need = max(0, max(tasks[i]) - curr_energy)\n            borrowed += need\n            curr_energy = curr_energy + need - tasks[i][0]\n\n        return borrowed
[]