Greedy Algorithms - Learn Step by Step

🤔 Why Master Greedy Algorithms?

🏪 Store Change Making

Cashiers use greedy approach - always give the largest denomination possible. Works perfectly for standard currency systems!

📅 Meeting Room Scheduling

Schedule maximum meetings by always picking the one that ends earliest. Simple rule, optimal results!

🗜️ File Compression

Huffman coding creates optimal compression by greedily merging least frequent characters first.

🛣️ GPS Navigation

Dijkstra's algorithm finds shortest paths by greedily exploring nearest unvisited nodes.

💡 The Greedy Philosophy

"Make the best choice now, never look back!"

Unlike dynamic programming, greedy algorithms never reconsider choices. This makes them fast but requires careful analysis to ensure correctness.

🌟 Greedy Fundamentals

Core Properties

✅ Greedy Choice Property

Making locally optimal choices leads to a globally optimal solution

🔗 Optimal Substructure

Optimal solution contains optimal solutions to subproblems

🚫 No Backtracking

Once a choice is made, it's never reconsidered

Classic Activity Selection 🎯

def activity_selection(activities):
    """
    Select maximum number of non-overlapping activities
    Greedy strategy: Always pick activity that finishes earliest
    Time: O(n log n), Space: O(1)
    """
    # Sort by finish time - this is the key insight!
    activities.sort(key=lambda x: x[1])
    
    selected = [activities[0]]  # Always pick first activity
    last_finish = activities[0][1]
    
    for i in range(1, len(activities)):
        start, finish = activities[i]
        if start >= last_finish:  # No overlap!
            selected.append(activities[i])
            last_finish = finish
    
    return selected

# Example: (start_time, finish_time)
activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9)]
print(f"Selected: {activity_selection(activities)}")
# Output: [(1, 4), (5, 7)] - Maximum activities!
                            

Fractional Knapsack 🎒

def fractional_knapsack(items, capacity):
    """
    Maximize value with fractional items allowed
    Greedy strategy: Sort by value-to-weight ratio
    """
    # Sort by value/weight ratio (highest first)
    items.sort(key=lambda x: x[1]/x[0], reverse=True)
    
    total_value = 0
    result = []
    
    for weight, value, name in items:
        if capacity >= weight:
            # Take entire item
            capacity -= weight
            total_value += value
            result.append((name, 1.0, value))
        else:
            # Take fraction of item
            fraction = capacity / weight
            total_value += value * fraction
            result.append((name, fraction, value * fraction))
            break
    
    return total_value, result

# Items: (weight, value, name)
items = [(10, 60, 'Gold'), (20, 100, 'Silver'), (30, 120, 'Gems')]
value, selection = fractional_knapsack(items, 50)
print(f"Max value: {value}")
                            

🎯 Greedy vs Dynamic Programming

Greedy: Make best local choice, never reconsider

DP: Consider all choices, build optimal solution from subproblems

When to use Greedy: When local optimal choices guarantee global optimum!

🎮 Interactive Greedy Demo

Activity Selection Visualizer

Click "Generate Random Activities" to start the demo!

Coin Change Demo

Enter an amount and click "Make Change" to see the greedy coin selection!

🌍 Real-World Applications

🏪 Store Checkout Systems

Problem: Give change with minimum coins

Greedy Solution: Always use largest denomination

Why it works: Standard currency is canonical

📅 Google Calendar

Problem: Schedule maximum meetings

Greedy Solution: Pick meetings ending earliest

Impact: Optimal scheduling in O(n log n)

🗜️ ZIP File Compression

Problem: Compress files efficiently

Greedy Solution: Huffman coding

Result: Optimal prefix-free codes

🚗 GPS Navigation

Problem: Find shortest path

Greedy Solution: Dijkstra's algorithm

Strategy: Always explore nearest unvisited node

🏭 Task Scheduling

Problem: Maximize profit with deadlines

Greedy Solution: Sort by profit, assign latest slot

Application: CPU job scheduling

🌐 Network Routing

Problem: Build minimum spanning tree

Greedy Solution: Prim's/Kruskal's algorithms

Use Case: Network infrastructure planning

Huffman Coding in Action 🗜️

import heapq
from collections import 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 build_huffman_tree(text):
    """Build Huffman tree using greedy merging"""
    freq = Counter(text)
    heap = [HuffmanNode(char, f) for char, f in freq.items()]
    heapq.heapify(heap)
    
    # Greedy: Always merge two nodes with smallest frequency
    while len(heap) > 1:
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        merged = HuffmanNode(freq=left.freq + right.freq, 
                           left=left, right=right)
        heapq.heappush(heap, merged)
    
    return heap[0] if heap else None

# Example: "hello" → Optimal compression!
text = "hello world"
root = build_huffman_tree(text)
# Creates optimal prefix-free codes automatically
                            

🚀 Advanced Greedy Techniques

Dijkstra's Algorithm 🛣️

import heapq
from collections import defaultdict

def dijkstra(graph, start):
    """
    Shortest path using greedy choice
    Always expand closest unvisited vertex
    Time: O((V + E) log V), Space: O(V)
    """
    distances = defaultdict(lambda: float('inf'))
    distances[start] = 0
    pq = [(0, start)]
    visited = set()
    parent = {}
    
    while pq:
        current_dist, u = heapq.heappop(pq)
        
        if u in visited:
            continue
        visited.add(u)
        
        # Greedy: Process all neighbors of closest node
        for v, weight in graph[u].items():
            if v not in visited:
                new_dist = current_dist + weight
                if new_dist < distances[v]:
                    distances[v] = new_dist
                    parent[v] = u
                    heapq.heappush(pq, (new_dist, v))
    
    return dict(distances), parent

# Example graph
graph = {
    'A': {'B': 4, 'C': 2},
    'B': {'D': 3},
    'C': {'B': 1, 'D': 5},
    'D': {}
}

distances, paths = dijkstra(graph, 'A')
print(f"Shortest distances: {distances}")
                            

Job Scheduling with Deadlines 📅

def job_scheduling_with_profit(jobs):
    """
    Maximize profit while meeting deadlines
    Greedy: Sort by profit, assign to latest possible slot
    """
    # Sort by profit (descending)
    jobs.sort(key=lambda x: x[1], reverse=True)
    
    max_deadline = max(job[2] for job in jobs)
    schedule = [None] * max_deadline
    total_profit = 0
    
    for job_id, profit, deadline in jobs:
        # Find latest available slot before deadline
        for slot in range(min(deadline - 1, max_deadline - 1), -1, -1):
            if schedule[slot] is None:
                schedule[slot] = job_id
                total_profit += profit
                break
    
    return [job for job in schedule if job], total_profit

# Jobs: (id, profit, deadline)
jobs = [('J1', 100, 2), ('J2', 19, 1), ('J3', 27, 2), ('J4', 25, 1)]
selected, profit = job_scheduling_with_profit(jobs)
print(f"Jobs: {selected}, Total profit: {profit}")
                            

⚠️ When Greedy Fails

0/1 Knapsack: Need dynamic programming
Longest Path Problem: NP-hard, no greedy solution
Some Coin Systems: May need more coins than optimal
Graph Coloring: Greedy gives approximation, not optimal

💪 Practice Problems

🟢 Easy: Activity Selection ▼

Problem: Given activities with start and end times, select maximum non-overlapping activities.

Input: [(1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11), (8,12), (2,14), (12,16)]

Strategy: Sort by finish time, greedily pick non-overlapping ones.

def max_activities(activities):
    activities.sort(key=lambda x: x[1])  # Sort by end time
    count = 1
    last_end = activities[0][1]
    
    for i in range(1, len(activities)):
        if activities[i][0] >= last_end:
            count += 1
            last_end = activities[i][1]
    
    return count
                            

🟡 Medium: Gas Station Circuit ▼

Problem: Find starting gas station to complete circular route.

Key Insight: If total gas ≥ total cost, solution exists. Start where deficit becomes 0.

def can_complete_circuit(gas, cost):
    total_tank = 0
    current_tank = 0
    start = 0
    
    for i in range(len(gas)):
        total_tank += gas[i] - cost[i]
        current_tank += gas[i] - cost[i]
        
        # If tank goes negative, can't start from earlier stations
        if current_tank < 0:
            start = i + 1
            current_tank = 0
    
    return start if total_tank >= 0 else -1
                            

🔴 Hard: Task Scheduler with Cooldown ▼

Problem: Schedule tasks with cooldown period between same tasks.

Strategy: Greedily schedule most frequent tasks first, use cooldown slots optimally.

def least_interval(tasks, n):
    from collections import Counter
    import heapq
    
    counts = Counter(tasks)
    heap = [-count for count in counts.values()]
    heapq.heapify(heap)
    
    time = 0
    
    while heap:
        temp = []
        
        # Try to schedule n+1 tasks (including cooldown)
        for i in range(n + 1):
            if heap:
                temp.append(heapq.heappop(heap))
        
        # Add back remaining tasks
        for count in temp:
            if count < -1:
                heapq.heappush(heap, count + 1)
        
        # Add time: full cycle if more tasks, else just scheduled
        time += (n + 1) if heap else len(temp)
    
    return time
                            

🎯 Mastery Checklist

✅ Can identify when greedy approach works
✅ Understand greedy choice property
✅ Can prove greedy correctness
✅ Know when greedy fails and alternatives needed
✅ Can implement efficiently with right data structures