Greedy Algorithms

12 min read

The Art of Making the Best Choice Right Now #

Think Like a Smart Shopper!

Imagine you’re at a buffet with limited stomach space, and you want to get the maximum satisfaction from your meal. What do you do? You probably pick the most delicious-looking items first, right? You don’t overthink it – you just grab what looks best at the moment.

This is exactly how greedy algorithms work! They make the locally optimal choice at each step, hoping that these choices will lead to a globally optimal solution. It’s like being that friend who always picks the biggest slice of pizza without considering if others might want some too – sometimes it works perfectly, sometimes… not so much! 😄

The Greedy Philosophy: “Live in the Moment” #

The Core Principle #

At each step, make the choice that looks best right now. Don’t worry about future consequences – just pick the option that gives you the maximum immediate benefit.

The Greedy Choice Property #

Once you make a choice, you never need to reconsider it. It’s like choosing your college major – once you decide, you commit and move forward (hopefully you chose wisely!).

Why This Can Work (And Sometimes Doesn’t) #

  • When it works: The problem has optimal substructure – local optimal choices lead to global optimal solutions
  • When it fails: Being greedy now might block better opportunities later

Real-World Greedy Scenarios #

The Good Greedy #

  • Traffic lights: Always let the longest queue go first
  • Emergency room: Treat the most critical patients first
  • Cashier making change: Give the largest denomination coins first

The Bad Greedy #

  • Job interviews: Taking the first decent offer might make you miss a dream job later
  • Stock trading: Selling at the first profit might cost you bigger gains
  • Route planning: Taking the fastest immediate road might lead to traffic jams

Classic Greedy Problems (With Real-Life Twists!) #

1. The Fractional Knapsack: Smart Shopping Spree #

You’re at a sample sale with a small bag, and you want to maximize the value of items you take home. Unlike the classic knapsack problem, you can take fractions of items (think liquid perfumes, loose jewelry, etc.).

def fractional_knapsack(items, capacity):
    """
    items: list of (value, weight) tuples
    capacity: maximum weight we can carry
    """
    # Calculate value-to-weight ratio for each item
    # Like calculating "bang for your buck"
    items_with_ratio = []
    for i, (value, weight) in enumerate(items):
        ratio = value / weight
        items_with_ratio.append((ratio, value, weight, i))
    
    # Sort by ratio in descending order (greediest first!)
    items_with_ratio.sort(reverse=True)
    
    total_value = 0
    total_weight = 0
    result = []
    
    print("Shopping strategy:")
    for ratio, value, weight, index in items_with_ratio:
        if total_weight + weight <= capacity:
            # Take the whole item
            total_weight += weight
            total_value += value
            result.append((index, 1.0))  # Take 100%
            print(f"✅ Take full item {index}: ${value} (ratio: ${ratio:.2f}/kg)")
        elif total_weight < capacity:
            # Take fraction of the item
            remaining_capacity = capacity - total_weight
            fraction = remaining_capacity / weight
            total_weight += remaining_capacity
            total_value += value * fraction
            result.append((index, fraction))
            print(f"🔄 Take {fraction:.1%} of item {index}: ${value * fraction:.2f}")
            break
        else:
            print(f"❌ Skip item {index}: bag is full")
    
    return total_value, result

# Example: Sample sale items (value, weight)
sale_items = [
    (60, 10),   # Designer perfume: $60, 10kg
    (100, 20),  # Jewelry set: $100, 20kg  
    (120, 30),  # Handbag: $120, 30kg
]

max_value, selection = fractional_knapsack(sale_items, 50)
print(f"\n💰 Maximum value achieved: ${max_value}")

Why greedy works here: Items with higher value-to-weight ratios are always better choices, no matter what comes later.

2. Activity Selection: The Ultimate Schedule Optimizer #

You’re a busy student with multiple club meetings, study sessions, and social events. You want to attend the maximum number of activities without conflicts.

def activity_selection(activities):
    """
    activities: list of (activity_name, start_time, end_time)
    """
    # Sort by end time (finish earliest first - that's the greedy choice!)
    activities.sort(key=lambda x: x[2])
    
    selected = []
    last_end_time = 0
    
    print("📅 Schedule optimization:")
    print("Available activities (sorted by end time):")
    for name, start, end in activities:
        print(f"  {name}: {start}:00 - {end}:00")
    
    print("\nSelection process:")
    for name, start, end in activities:
        if start >= last_end_time:
            selected.append((name, start, end))
            last_end_time = end
            print(f"✅ Selected: {name} ({start}:00 - {end}:00)")
        else:
            print(f"❌ Skipped: {name} (conflicts with previous activity)")
    
    return selected

# Example: Student's daily activities
student_activities = [
    ("Math Study Group", 9, 11),
    ("Gym Session", 10, 12),
    ("Lunch with Friends", 12, 13),
    ("Programming Club", 13, 15),
    ("Basketball Practice", 14, 16),
    ("Part-time Job", 16, 18),
    ("Dinner Date", 17, 19),
    ("Movie Night", 19, 21)
]

optimal_schedule = activity_selection(student_activities)
print(f"\n🎯 Optimal schedule: {len(optimal_schedule)} activities")
for activity in optimal_schedule:
    print(f"  • {activity[0]}: {activity[1]}:00 - {activity[2]}:00")

The greedy insight: Always pick the activity that finishes earliest – this leaves maximum room for future activities!

3. Huffman Coding: The Text Compression Wizard #

Imagine you’re sending text messages and want to minimize data usage. Huffman coding assigns shorter codes to frequently used characters.

import heapq
from collections import defaultdict, Counter

class HuffmanNode:
    def __init__(self, char=None, freq=0, left=None, right=None):
        self.char = char
        self.freq = freq
        self.left = left
        self.right = right
    
    def __lt__(self, other):
        return self.freq < other.freq

def huffman_encoding(text):
    # Count frequency of each character
    frequency = Counter(text)
    print(f"📊 Character frequencies in '{text}':")
    for char, freq in sorted(frequency.items()):
        print(f"  '{char}': {freq} times")
    
    # Create a priority queue (min-heap) of nodes
    heap = []
    for char, freq in frequency.items():
        node = HuffmanNode(char, freq)
        heapq.heappush(heap, node)
    
    # Build the Huffman tree (greedy: always combine two least frequent)
    print("\n🌳 Building Huffman tree:")
    step = 1
    while len(heap) > 1:
        # Take two nodes with minimum frequency
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        
        print(f"  Step {step}: Combine freq {left.freq} + {right.freq} = {left.freq + right.freq}")
        
        # Create new internal node
        merged = HuffmanNode(freq=left.freq + right.freq, left=left, right=right)
        heapq.heappush(heap, merged)
        step += 1
    
    # Generate codes
    root = heap[0]
    codes = {}
    
    def generate_codes(node, code=""):
        if node.char:  # Leaf node
            codes[node.char] = code if code else "0"  # Handle single character case
        else:
            generate_codes(node.left, code + "0")
            generate_codes(node.right, code + "1")
    
    generate_codes(root)
    
    # Encode the text
    encoded = "".join(codes[char] for char in text)
    
    print(f"\n🔢 Huffman codes:")
    for char, code in sorted(codes.items()):
        print(f"  '{char}': {code}")
    
    print(f"\n📱 Original text: '{text}' ({len(text) * 8} bits in ASCII)")
    print(f"📱 Encoded text: '{encoded}' ({len(encoded)} bits)")
    print(f"💾 Compression ratio: {len(encoded)/(len(text)*8):.2%}")
    
    return encoded, codes

# Example: Compress a message
message = "hello world"
compressed, codes = huffman_encoding(message)

Greedy strategy: Always combine the two least frequent nodes first. This ensures frequently used characters get shorter codes!

4. Coin Change: The Smart Cashier #

You’re a cashier and need to give change using the minimum number of coins. This works perfectly with standard coin systems!

def greedy_coin_change(amount, coins):
    """
    amount: money to return
    coins: available coin denominations (must be sorted in descending order)
    """
    result = []
    total_coins = 0
    
    print(f"💰 Making change for ${amount}")
    print(f"Available coins: {coins}")
    print("\nGreedy selection process:")
    
    for coin in coins:
        if amount >= coin:
            count = amount // coin
            if count > 0:
                result.append((coin, count))
                amount -= coin * count
                total_coins += count
                print(f"  Use {count} × ${coin} coins (remaining: ${amount})")
    
    if amount > 0:
        print(f"❌ Cannot make exact change! Remaining: ${amount}")
        return None
    
    print(f"✅ Total coins needed: {total_coins}")
    return result

# Example: US coin system
us_coins = [25, 10, 5, 1]  # quarters, dimes, nickels, pennies
change_needed = 67

coin_breakdown = greedy_coin_change(change_needed, us_coins)
if coin_breakdown:
    print("\n🪙 Final breakdown:")
    for coin_value, count in coin_breakdown:
        coin_name = {25: "quarters", 10: "dimes", 5: "nickels", 1: "pennies"}[coin_value]
        print(f"  {count} {coin_name} (${coin_value * count})")

Important note: This greedy approach only works with certain coin systems (like US coins). With some coin systems, being greedy might not give the minimum number of coins!

5. Job Scheduling: The Deadline Master #

You have multiple assignments with different deadlines and penalties. You want to minimize the total penalty for late submissions.

def job_scheduling_with_deadlines(jobs):
    """
    jobs: list of (job_name, deadline, penalty) tuples
    """
    # Sort by penalty in descending order (highest penalty first - greedy!)
    jobs.sort(key=lambda x: x[2], reverse=True)
    
    print("📚 Assignment scheduling problem:")
    print("Jobs sorted by penalty (highest first):")
    for name, deadline, penalty in jobs:
        print(f"  {name}: deadline day {deadline}, penalty ${penalty}")
    
    # Find maximum deadline to know our time slots
    max_deadline = max(job[1] for job in jobs)
    
    # Schedule array: schedule[i] represents what job is done on day i+1
    schedule = [None] * max_deadline
    total_penalty = 0
    scheduled_jobs = []
    
    print(f"\n⏰ Available time slots: {max_deadline} days")
    print("\nScheduling process:")
    
    for name, deadline, penalty in jobs:
        # Try to schedule this job as late as possible (but before deadline)
        scheduled = False
        for day in range(min(deadline, max_deadline) - 1, -1, -1):
            if schedule[day] is None:
                schedule[day] = name
                scheduled_jobs.append((name, day + 1, penalty))
                print(f"✅ Schedule '{name}' on day {day + 1}")
                scheduled = True
                break
        
        if not scheduled:
            total_penalty += penalty
            print(f"❌ Cannot schedule '{name}' - penalty: ${penalty}")
    
    print(f"\n📅 Final schedule:")
    for day in range(max_deadline):
        if schedule[day]:
            print(f"  Day {day + 1}: {schedule[day]}")
        else:
            print(f"  Day {day + 1}: Free time")
    
    print(f"\n💸 Total penalty for missed deadlines: ${total_penalty}")
    return scheduled_jobs, total_penalty

# Example: Student assignments
assignments = [
    ("Math Homework", 3, 40),
    ("History Essay", 1, 35),
    ("Science Project", 2, 30),
    ("Art Portfolio", 3, 25),
    ("Programming Assignment", 2, 20)
]

scheduled, penalty = job_scheduling_with_deadlines(assignments)

Greedy insight: Handle high-penalty jobs first, and schedule each job as late as possible (but still on time) to leave room for other jobs!

6. Minimum Spanning Tree: The Network Builder #

You’re planning to connect multiple cities with the cheapest possible network of roads. You want all cities connected with minimum total cost.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

def kruskal_mst(cities, roads):
    """
    cities: list of city names
    roads: list of (city1_index, city2_index, cost) tuples
    """
    # Sort roads by cost (cheapest first - greedy!)
    roads.sort(key=lambda x: x[2])
    
    print("🏗️  Building minimum cost road network:")
    print("Available roads (sorted by cost):")
    for city1, city2, cost in roads:
        print(f"  {cities[city1]} ↔ {cities[city2]}: ${cost}M")
    
    uf = UnionFind(len(cities))
    mst = []
    total_cost = 0
    
    print(f"\n🛣️  Road selection process:")
    
    for city1, city2, cost in roads:
        if uf.union(city1, city2):
            mst.append((city1, city2, cost))
            total_cost += cost
            print(f"✅ Build: {cities[city1]} ↔ {cities[city2]} (${cost}M)")
        else:
            print(f"❌ Skip: {cities[city1]} ↔ {cities[city2]} (would create cycle)")
    
    print(f"\n🌐 Final network:")
    print(f"Total roads built: {len(mst)}")
    print(f"Total cost: ${total_cost}M")
    
    return mst, total_cost

# Example: Connecting 5 cities
city_names = ["New York", "Boston", "Philadelphia", "Washington", "Baltimore"]
possible_roads = [
    (0, 1, 100),  # NY-Boston: $100M
    (0, 2, 80),   # NY-Philadelphia: $80M
    (0, 3, 120),  # NY-Washington: $120M
    (1, 2, 70),   # Boston-Philadelphia: $70M
    (1, 4, 90),   # Boston-Baltimore: $90M
    (2, 3, 50),   # Philadelphia-Washington: $50M
    (2, 4, 60),   # Philadelphia-Baltimore: $60M
    (3, 4, 40),   # Washington-Baltimore: $40M
]

network, cost = kruskal_mst(city_names, possible_roads)

Greedy strategy: Always pick the cheapest available road that doesn’t create a cycle. This guarantees the minimum total cost!

When Greedy Works vs. When It Doesn’t #

✅ Greedy Works Great For: #

1. Optimization problems with greedy choice property

  • Activity selection
  • Fractional knapsack
  • Huffman coding

2. Problems where local optimum = global optimum

  • Making change with standard coin systems
  • Finding minimum spanning trees

❌ Greedy Fails For: #

1. 0/1 Knapsack Problem

# Example where greedy fails
items = [(10, 5), (40, 4), (30, 6), (50, 3)]  # (value, weight)
capacity = 10

# Greedy by value/weight ratio would pick:
# Item 4 (ratio: 16.67), Item 2 (ratio: 10) → Total value: 90
# But optimal is: Item 2 + Item 3 → Total value: 70

# Wait, that doesn't look right! Let me recalculate...
# Actually, greedy gives: (50,3) + (40,4) = value 90, weight 7
# Alternative: (40,4) + (30,6) = value 70, weight 10
# So greedy actually works here! Bad example 😅

2. Shortest Path with Negative Weights Greedy algorithms like Dijkstra’s fail when there are negative edge weights.

3. Coin Change with Arbitrary Denominations

# Example: coins = [1, 3, 4], amount = 6
# Greedy: 4 + 1 + 1 = 3 coins
# Optimal: 3 + 3 = 2 coins

Pro Tips for Greedy Success #

1. Identify the Greedy Choice #

What’s the “obvious best” choice at each step? Usually involves:

  • Maximum/minimum values
  • Ratios or rates
  • Earliest/latest times

2. Prove It Works (Or Test Extensively) #

  • Show that your greedy choice is always safe
  • Verify with multiple test cases
  • Consider edge cases

3. Sort Your Data First #

Most greedy algorithms start with sorting:

  • By value, weight, ratio, time, etc.
  • This often reveals the optimal order for making choices

4. Watch Out for Counterexamples #

Always try to think of cases where being greedy might backfire!

Common Greedy Algorithm Patterns #

1. The “Take the Best Available” Pattern #

  • Fractional knapsack
  • Activity selection
  • Job scheduling

2. The “Cheapest First” Pattern #

  • Minimum spanning tree
  • Shortest path (Dijkstra’s)

3. The “Deadline-Driven” Pattern #

  • Job scheduling with deadlines
  • Task prioritization

4. The “Frequency-Based” Pattern #

  • Huffman coding
  • Load balancing

Practice Problems to Master Greedy Thinking #

Beginner Level: #

  1. Gas Station Problem: Can you complete a circular route?
  2. Meeting Rooms: Maximum non-overlapping meetings
  3. Candy Distribution: Minimum candies to satisfy children

Intermediate Level: #

  1. Jump Game: Can you reach the end of the array?
  2. Container With Most Water: Maximum area between lines
  3. Non-overlapping Intervals: Minimum removals to make non-overlapping

Advanced Level: #

  1. Course Schedule: Task scheduling with prerequisites
  2. Minimum Number of Arrows: Burst all balloons
  3. Partition Labels: Partition string into maximum parts

Conclusion: The Art of Strategic Impatience #

Greedy algorithms teach us that sometimes the best strategy is to trust our instincts and make the obviously good choice right now. It’s like being strategically impatient – instead of overthinking every possibility, you grab the best option available and move forward.

The key to mastering greedy algorithms is developing an intuition for when “locally optimal” leads to “globally optimal.” It’s not always true, but when it is, greedy algorithms give you elegant, efficient solutions that are often easier to understand and implement than their more complex alternatives.

Remember: being greedy in algorithms is usually good, but being greedy in real life… well, that’s a different story! 😄

The Greedy Mindset:

  • Trust the obvious best choice
  • Don’t second-guess yourself
  • Move fast and don’t look back
  • But always verify your strategy works!

Happy coding, and may your algorithms always make the right greedy choices! 🎯

Updated on June 9, 2025