Greedy
147 / 170GreedyLesson 1 of 9About 42 min
The question the last two units earned you the right to ask, on a problem where the obvious greedy rule is wrong.
You solved the fewest-pieces problem with a table in Unit 14. The obvious greedy rule is to take the largest piece that fits, repeatedly. On ordinary currency it works. On other sets it does not.
def greedy_count(target, sizes): remaining, used = target, 0 for size in sorted(sizes, reverse=True): while size <= remaining: remaining -= size used += 1 return used if remaining == 0 else -1 def table_count(target, sizes): INF = float("inf") best = [0] + [INF] * target for amount in range(1, target + 1): for size in sizes: if size <= amount: best[amount] = min(best[amount], best[amount - size] + 1) return best[target] if best[target] != INF else -1 print(greedy_count(30, [1, 15, 25]), table_count(30, [1, 15, 25]))print(greedy_count(6, [1, 3, 4]), table_count(6, [1, 3, 4]))State the rule in one sentence. Construct the exchange argument, or admit you cannot. Then look for a counterexample specifically designed to break it, the way the piece sets above were.
If the exchange argument holds, write the single pass. If it does not, you are in Unit 14 territory and need a table.
You must select the largest possible number of non-overlapping meetings from a list. Which greedy rule has a valid exchange argument?
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.