13 September 2018: Greedy Algorithms
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.
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)
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)
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)