# 13 September 2018: Greedy Algorithms

Jump to navigation
Jump to search

## Contents

## Elements of a Greedy Strategy

**Greedy-choice property:**There is always an optimal solution that makes the greedy choice.**Optimal substructure:**Making the greedy choice leaves us with a sub-problem, and solving the sub-problem optimally gives us an optimal solution to the original problem.

## Proving Greedy-Choice Property

The greedy problem-solving strategy often leads to very efficient algorithms, but proving the correctness of a greedy solution can be challenging. You should never waste time coding a solution that you haven't proved to be correct.

Proving the greedy choice is safe can usually be done with a * greedy-substitution proof*:

- Assume there is an optimal solution that does not include the greedy choice.
- Show that you can substitute in the greedy choice without making it any worse.

## Planting Trees

https://vjudge.net/problem/Kattis-plantingtrees

```
N = int(input())
T = [int(t) for t in input().split()]
T.sort()
T.reverse()
ans = 1
for i, t in enumerate(T):
ans = max(ans, i + t + 2)
print(ans)
```

## Watering Grass

https://vjudge.net/problem/Kattis-grass

```
from math import sqrt
while True:
try:
n, l, w = map(int, input().split())
except:
break
S = []
for _ in range(n):
x, r = map(int, input().split())
if 2*r > w:
x0 = max([0, x - sqrt(r*r - (w/2)*(w/2))])
x1 = min([l, x + sqrt(r*r - (w/2)*(w/2))])
S.append((x0, x1))
S.sort()
ans, R, i = 0, 0, 0
while i < len(S) and S[i][0] <= R:
nextR = 0
while i < len(S) and S[i][0] <= R:
nextR = max(nextR, S[i][1])
i += 1
if nextR > R:
R = nextR
ans += 1
print(ans if R == l else -1)
```

## Bank Queue

https://vjudge.net/problem/Kattis-bank

```
import heapq
N, T = map(int, input().split())
C = []
for _ in range(N):
c, t = map(int, input().split())
C.append((t, c))
C.sort()
C.reverse()
pq = []
ans = 0
i = 0
for t in reversed(range(T+1)):
while i < N and C[i][0] >= t:
heapq.heappush(pq, -C[i][1])
i += 1
if pq:
ans -= heapq.heappop(pq)
T -= 1
print(ans)
```