# 13 September 2018: Greedy Algorithms

Jump to navigation Jump to search

## Elements of a Greedy Strategy

1. Greedy-choice property: There is always an optimal solution that makes the greedy choice.
2. 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:

1. Assume there is an optimal solution that does not include the greedy choice.
2. 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] <= R:
nextR = 0
while i < len(S) and S[i] <= R:
nextR = max(nextR, S[i])
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] >= t:
heapq.heappush(pq, -C[i])
i += 1
if pq:
ans -= heapq.heappop(pq)
T -= 1

print(ans)