Proof with induction
Assertion: if x as initial energy can finish all tasks in some order, then it must be sufficient to finish all tasks in descending order by (minium \u2013 actua
Assertion: if x as initial energy can finish all tasks in some order, then it must be sufficient to finish all tasks in descending order by (minium \u2013 actual).\n\nProof:\nIf there is 1 task, the assertion is obviously true.\n\nIf there are 2 tasks, let\u2019s say we have: [a, a + c1] and [b, b + c2], and c1 >= c2.\nIf we can finish tasks by finishing by order (b, a), then we must have:\n1) x >= b + c2 (b can start)\n2) x  - b >= a + c1 (after b, a can start).\nSo we have: x \u2013 b >= a + c1 => x \u2013 a >= b + c1 >= b + c2\nThis means we can complete task a first and then b.\n\nIf there are N tasks and we can finish them in some order that\u2019s different than the above sorting order.\nLet m be the first task not in the above sorting order, that is (D = minimu - actual):\n(i)\tD1 >= D2 >= \u2026 >= Dm-1 < Dm\nSuppose the right position for Dm to be in order is k, that is:\n(ii) D1 >= D2 >= \u2026 >= Dk >= Dm >= Dk+1 >= \u2026 >= Dm-1\nWhat we should prove is that if we can finish tasks in order (i) with initial energy x, we can finish them in order (ii) with x.\nWe can do this by:\n-\tFirst, swapping Dm-1 and Dm in (i), we have (\u2026., Dk, Dk+1, \u2026,Dm-2, Dm, Dm-1). Because Dm > Dm-1, based on the above case where N=2, we must be able to finish taks in this order.\n    Note: the preceeding m \u2013 2 tasks are unchanged and are still in order of (D1, D2, \u2026, Dk, Dk+1, \u2026, Dm-2), so if we start with initial energy x, we will have same remaining energy after finishing these m-2 tasks. That is, we are using the same initial energy for processing original (Dm-1, Dm) and the swapped (Dm, Dm-1), therefore can apply the conclusion above with N=2 tasks.\n-\tThen we swap Dm-2 and Dm, we have (\u2026., Dk, Dk+1, \u2026, Dm, Dm-2, Dm-1). And for the same reason we can finish tasks in this order as well.\n-\tKeep swapping, we will have (\u2026, Dk, Dm, Dk+1, \u2026, Dm-2, Dm-1). We can also finish this task order. And this one is sorted by descending of D.\nHereby we proved that the assertion holds when there are N tasks.\n
[]