Problem: find the minimum number of coins for amount k
Greedy works only when denominationi is divisible by denominationi-1, i>=2
Otherwise, you should use DP.
import sys
n, k = map(int, sys.stdin.readline().split())
denominations = []
for _ in range(n):
denominations.append(int(sys.stdin.readline()))
count = 0
for coin in denominations[::-1]:
count += k//coin
k = k%coin
print(count)
Problem: find the maximum-size subset of mutually compatible intervals
Consider intervals in increasing order of finish time
import sys
n = int(sys.stdin.readline())
intervals = []
for _ in range(n):
s, e = map(int, sys.stdin.readline().split())
intervals.append((s, e))
intervals.sort(key=lambda x: (x[1], x[0]))
count = 0
prev = 0
for interval in intervals:
if interval[0] >= prev:
count += 1
prev = interval[1]
print(count)