13 September 2018: Greedy Algorithms

From UMCPC Wiki
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


N = int(input())
T = [int(t) for t in input().split()]


ans = 1

for i, t in enumerate(T):
    ans = max(ans, i + t + 2)


Watering Grass


from math import sqrt

while True:
        n, l, w = map(int, input().split())

    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))


    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


import heapq

N, T = map(int, input().split())

C = []

for _ in range(N):
    c, t = map(int, input().split())
    C.append((t, c))


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