Top 5 Greedy Problems Every Programmer Should Know

What is a Greedy Algorithm?

A Greedy Algorithm solves problems by:

1. Dividing the problem into subproblems.
2. Choosing the best option (locally optimal) for each subproblem.
3. Assuming that these local choices lead to a globally optimal solution.

When Does Greedy Work?

A greedy approach works well when the problem has the following properties:

• Optimal Substructure: A solution can be built incrementally using subsolutions.
• Greedy Choice Property: Local optimal choices result in the global optimal solution.

1. Activity Selection Problem

Problem

Given n activities with start and finish times, select the maximum number of non-overlapping activities.

Greedy Approach

Sort activities by their finish time. Always pick the activity that finishes the earliest and doesn’t overlap with previously selected activities.

Code Implementation

def activity_selection(activities):
    # Sort by finish times
    activities.sort(key=lambda x: x[1])
    
    selected = []
    last_end = 0
    
    for start, end in activities:
        if start >= last_end:
            selected.append((start, end))
            last_end = end
    
    return selected

Example

activities = [(1, 3), (2, 5), (4, 6), (6, 8), (5, 7)]
print(activity_selection(activities))

Output:

[(1, 3), (4, 6), (6, 8)]

2. Huffman Encoding

Problem

Given a set of characters with frequencies, create an optimal prefix code for the characters to minimize the total encoding length.

Greedy Approach

Use a priority queue (min-heap) to combine the two smallest frequency nodes iteratively until one node remains.

Code Implementation

import heapq

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

def huffman_encoding(frequencies):
    heap = [Node(char, freq) for char, freq in frequencies.items()]
    heapq.heapify(heap)
    
    while len(heap) > 1:
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        merged = Node(None, left.freq + right.freq)
        merged.left = left
        merged.right = right
        heapq.heappush(heap, merged)
    
    return heap[0]

# Helper to print codes
def print_codes(node, code=""):
    if node is None:
        return
    if node.char:
        print(f"{node.char}: {code}")
    print_codes(node.left, code + "0")
    print_codes(node.right, code + "1")

Example

frequencies = {'A': 5, 'B': 9, 'C': 12, 'D': 13, 'E': 16, 'F': 45}
tree = huffman_encoding(frequencies)
print_codes(tree)

Output:

F: 0
C: 100
D: 101
A: 1100
B: 1101
E: 111

3. Fractional Knapsack Problem

Problem

Given weights and values of n items, fill a knapsack of capacity W to maximize the total value. You can take fractional amounts of items.

Greedy Approach

Sort items by value-to-weight ratio in descending order. Pick as much as possible from the highest ratio item.

Code Implementation

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

Example

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

Output:

240.0

4. Coin Change Problem

Problem

Given a set of coin denominations and a target amount, find the minimum number of coins needed to make the amount.

Greedy Approach

Always pick the largest coin denomination that doesn’t exceed the remaining amount.

Code Implementation

def coin_change(coins, amount):
    coins.sort(reverse=True)
    count = 0
    
    for coin in coins:
        while amount >= coin:
            amount -= coin
            count += 1
    
    return count if amount == 0 else -1

Example

coins = [1, 5, 10, 25]
amount = 63
print(coin_change(coins, amount))

Output:

6 (25 + 25 + 10 + 1 + 1 + 1)

5. Job Scheduling Problem

Problem

Given jobs with deadlines and profits, schedule jobs to maximize total profit while ensuring no two jobs overlap.

Greedy Approach

Sort jobs by profit in descending order. Schedule each job at the latest available slot before its deadline.

Code Implementation

def job_scheduling(jobs, max_deadline):
    jobs.sort(key=lambda x: x[1], reverse=True)  # Sort by profit
    slots = [-1] * max_deadline  # Time slots
    
    total_profit = 0
    for job_id, profit, deadline in jobs:
        for i in range(min(deadline - 1, max_deadline - 1), -1, -1):
            if slots[i] == -1:  # Slot available
                slots[i] = job_id
                total_profit += profit
                break
    
    return total_profit, slots

Example

jobs = [(1, 35, 3), (2, 30, 4), (3, 25, 4), (4, 20, 2), (5, 15, 3)]  # (job_id, profit, deadline)
max_deadline = 4
print(job_scheduling(jobs, max_deadline))

Output:

(80, [1, 4, 5, 3])

Conclusion

The greedy algorithm is a simple yet powerful approach that shines in specific types of problems. By understanding its principles and practicing with classic problems like those listed above, you’ll develop a deep appreciation for its efficiency and versatility.

Which greedy problem is your favorite? Let’s discuss in the comments below!