DSA Greedy Algorithms

A greedy algorithm solves a problem by picking the best-looking option at every step. The algorithm never reconsiders earlier picks. Each local choice aims to build a good overall answer.

Imagine a cashier who must return 87 cents in change. The cashier grabs the largest coin that fits, repeats the move, and finishes quickly. Nobody plans the whole sequence ahead of time. The cashier simply takes the biggest coin each round.

How Greedy Thinking Works

• Define what "best" means for the current step.
• Pick the best option available right now.
• Lock in that choice permanently.
• Repeat until the problem is solved.

Greedy methods run fast because they skip backtracking and avoid comparing every combination.

Example: Coin Change

Standard coins are 25, 10, 5, and 1. The goal is to reach 63 using the fewest coins.

def make_change(amount, coins):
    result = []
    for coin in sorted(coins, reverse=True):
        while amount >= coin:
            amount -= coin
            result.append(coin)
    return result

print(make_change(63, [25, 10, 5, 1]))   # [25, 25, 10, 1, 1, 1]

Amount 63
take 25 -> left 38
take 25 -> left 13
take 10 -> left 3
take 1  -> left 2
take 1  -> left 1
take 1  -> left 0

Total coins = 6

When Greedy Fails

Greedy does not work for every problem. A different coin set exposes the weakness. With coins 1, 3, and 4, the target 6 shows the trouble.

Greedy picks: 4 + 1 + 1 = 3 coins
Best answer:  3 + 3     = 2 coins

The greedy choice of 4 looked great at first and blocked the better solution. Problems like this need dynamic programming instead.

When Greedy Works

Greedy succeeds when two properties hold.

• Greedy choice property: a locally best choice always fits inside some globally best answer.
• Optimal substructure: after making a choice, the leftover problem has the same form as the original.

Example: Activity Selection

A hall hosts events, and each event has a start and end time. Two events cannot overlap. The goal is to schedule the most events.

The winning rule picks the event that finishes earliest. An early finish leaves the most room for later events.

def max_events(events):
    events.sort(key=lambda e: e[1])    # sort by end time
    count = 0
    last_end = 0
    for start, end in events:
        if start >= last_end:
            count += 1
            last_end = end
    return count

events = [(1, 3), (2, 5), (4, 6), (6, 8), (5, 9)]
print(max_events(events))   # 3

Time:  1 2 3 4 5 6 7 8 9
(1,3)  [===]
(2,5)    [=====]
(4,6)        [===]
(6,8)            [===]
(5,9)          [=======]

Chosen: (1,3), (4,6), (6,8)

Example: Fractional Knapsack

A bag holds a limited weight. Each item has a value and a weight, and items can be split into smaller parts. Choosing items with the highest value per unit of weight gives the best total.

def fractional_knapsack(items, capacity):
    items.sort(key=lambda x: x[0] / x[1], reverse=True)
    total = 0
    for value, weight in items:
        if capacity >= weight:
            total += value
            capacity -= weight
        else:
            total += value * (capacity / weight)
            break
    return total

items = [(60, 10), (100, 20), (120, 30)]
print(fractional_knapsack(items, 50))   # 240.0

The bag takes all of the first two items and two thirds of the third item.

Complexity

Many greedy solutions begin with sorting, so the typical time cost is O(n log n). The picking loop adds O(n). Space usually stays at O(1) or O(n), based on the data stored.

Greedy vs Dynamic Programming

Both methods build answers from smaller pieces. Greedy commits to one choice and moves on, which keeps the code short and fast. Dynamic programming compares many choices and stores the results, which costs more memory and time but handles tricky cases. Test a greedy idea on small inputs before trusting it. A single counterexample, like the 1-3-4 coin set, proves the idea wrong.

Common Mistakes

Choosing the wrong sorting rule breaks many greedy solutions. Activity selection sorts by end time, and sorting by start time gives wrong answers. Assuming greedy always works is another trap. Write a tiny brute-force checker for small inputs and compare its answers with your greedy result. Matching answers across many test cases builds confidence in the rule.

Key Points

• Greedy algorithms pick the best local option at each step.
• Greedy picks are final, and the algorithm never undoes them.
• Greedy answers are optimal only when the problem has the greedy choice property.
• Coin change with unusual coins shows a case where greedy fails.
• Activity selection and fractional knapsack are textbook greedy successes.
• Sorting often forms the first step.