Greedy Algorithms in TheAlgorithms/Python

The greedy coin change algorithm works correctly when the denomination set is canonical, meaning each denomination is at least double the previous one or follows a specific structure that prevents suboptimal choices. Indian currency denominations (1, 2, 5, 10, 20, 50, 100, 200, 500, 2000) have this property, which is why the doctests use them. The algorithm reverses the sorted denomination list so the largest value comes first, then repeatedly subtracts each denomination from the remaining total for as long as the denomination fits. The inner while loop handles cases like 18745, where 2000 is used nine times before 500 becomes the next fit. This greedy approach fails for arbitrary denomination sets; a denomination set like (1, 3, 4) with target 6 would require a DP solution to find the optimal (3, 3) rather than the greedy (4, 1, 1).

The stock profit problem asks for the maximum single buy-sell pair profit given a price series. A naive solution tries every buy-sell pair in O(n squared). The greedy observation is that to maximize profit on a sell day, you want to have bought at the lowest price seen so far. The algorithm maintains two running values: min_price tracks the cheapest buy opportunity seen up to the current day, and max_profit tracks the best profit achievable so far. On each iteration, min_price is updated first so it reflects the cheapest price on or before the current day, then max_profit compares the profit from selling today against the current best. The second doctest confirms the correct handling of a monotonically decreasing price series: no profitable trade exists, so the answer is 0 rather than a negative value.

The gas station problem asks for a starting station from which a car can complete a circular route without running out of fuel. A brute-force solution tries every starting station in O(n squared). The greedy algorithm exploits a key insight: if total gas across all stations is at least total cost, a valid starting station is guaranteed to exist. Lines 80-81 compute both sums. If total gas falls short, the function returns -1 immediately. Otherwise it scans stations, tracking the running net gas from a candidate start. When net gas drops below 0, the candidate cannot work, so it resets to the next station and net gas resets to 0. Because global feasibility is confirmed, the final candidate is guaranteed valid. The GasStation dataclass pairs each station's gas quantity and travel cost.

Merging sorted files costs the sum of their sizes per pairwise merge. The order determines total cost because small files merged early are included in every subsequent merge. The greedy strategy is to always merge the two smallest files, minimizing small-file contributions. Each iteration calls files.index(min(files)) twice, removes both minimums, and appends their combined size. That combined size also accumulates into optimal_merge_cost. For files [2, 3, 4]: first merge combines 2 and 3 into 5 at cost 5; second merges 4 and 5 at cost 9; total is 14. A different order (merging 3 and 4 first) gives total 16. A production version would use a min-heap to replace the repeated O(n) scans with O(log n) extractions.