mathematical proof of greedy
Mathematical Proof of greedy

lets assume I have budget=budget


doing (a,b) first and then (c,d) is better or  doing (c,d) first and then (a,b). Assuming: d-c>
# Mathematical Proof of greedy
1. lets assume I have budget=budget
2. doing (a,b) first and then (c,d) is better or  doing (c,d) first and then (a,b). Assuming: d-c>=b-a 
3. if we prove that doing (c,d) first and then (a,b) is better, we actually proved greedy approach and why we sort and why we start from the one having greatest difference in actual_i and minimum_i

4. doing (c,d) first and then (a,b):
budget-d
budget-d+(d-c)
budget-d+(d-c)-b
budget-d+(d-c)-b+(b-a)
worst_we_get=min(budget-d,budget-b-c)
5. doing (a,b) first and then (c,d):
budget-b
budget-b+(b-a)
budget-b+(b-a)-d
budget-b+(b-a)-d+(d-c)
worst_we_get=min(budget-b,budget-a-d)
6. compare them and prove that
min(budget-d,budget-b-c)>=min(budget-b,budget-a-d)
equivalent to both of following two inequalities being true simultaneously
0>=min(c,b+c-a-d) correct as min(c,b+c-a-d)<=(b-a)-(d-c)
0>=min(d-b,-a) correct as min(d-b,-a)<=-a


# Complexity
- Time complexity:
O(n log n)

# Code
```python []
class Solution(object):
    def minimumEffort(self, tasks):
        tasks.sort(key=lambda (a,b):a-b)
        worst=float('inf')
        cur=0
        for a,b in tasks:
            cur-=b
            worst=min(worst,cur)
            cur+=b-a
        return -worst
        
        
```
['Python']