Greedy Algorithm Examples

1. Activity Selection Problem

Problem: Given n activities with start and end times, select the maximum number of activities that don’t overlap.

Greedy Approach:

  • Sort activities by their end times.
  • Always select the next activity that starts after the previous selected activity ends.

Pseudocode:

Input: Activities[] (each activity has start and end time)
Sort Activities[] by end time
selected = []
lastEnd = -∞

for activity in Activities:
    if activity.start >= lastEnd:
        selected.append(activity)
        lastEnd = activity.end

Output: selected

2. Coin Change Problem (Minimizing Coins)

Problem: Given denominations of coins and a target amount, find the minimum number of coins needed to make the amount (assuming an unlimited supply of coins).

Greedy Approach:

  • Use the highest denomination coin available without exceeding the target amount.

Pseudocode:

Input: denominations[], targetAmount
Sort denominations[] in descending order
coinsUsed = 0

for coin in denominations:
    while targetAmount >= coin:
        targetAmount -= coin
        coinsUsed += 1

if targetAmount == 0:
    Output: coinsUsed
else:
    Output: "Change cannot be made"

3. Fractional Knapsack Problem

Problem: Given weights and values of items, find the maximum total value in a knapsack of capacity W, where you can take fractional amounts of items.

Greedy Approach:

  • Calculate the value-to-weight ratio for each item.
  • Take items with the highest ratio first, taking as much as possible until the capacity is filled.

Pseudocode:

Input: items[] (each item has weight and value), capacity W
for each item in items:
    item.ratio = item.value / item.weight

Sort items[] by ratio in descending order
totalValue = 0

for item in items:
    if W == 0:
        break
    if item.weight <= W:
        totalValue += item.value
        W -= item.weight
    else:
        totalValue += item.value * (W / item.weight)
        W = 0

Output: totalValue

4. Huffman Encoding

Problem: Given a set of characters and their frequencies, create a binary prefix code (Huffman Code) that minimizes the total encoded string length.

Greedy Approach:

  • Build a tree by combining the two smallest frequency nodes iteratively.

Pseudocode:

Input: frequencies[] (list of character frequencies)
Create a priority queue PQ and insert all characters with their frequencies

while PQ.size > 1:
    left = PQ.pop()  # Smallest frequency node
    right = PQ.pop() # Second smallest frequency node
    combinedNode = newNode(frequency=left.frequency + right.frequency)
    combinedNode.left = left
    combinedNode.right = right
    PQ.push(combinedNode)

Output: PQ.top() # Root of the Huffman Tree

5. Dijkstra’s Algorithm (Shortest Path)

Problem: Find the shortest path from a source node to all other nodes in a graph with non-negative edge weights.

Greedy Approach:

  • Use a priority queue to always expand the node with the smallest distance from the source.

Pseudocode:

Input: graph[], source
dist[] = [∞] * size(graph)  # Distance to all nodes
dist[source] = 0
PriorityQueue PQ
PQ.push((0, source))  # (distance, node)

while PQ is not empty:
    currentDist, currentNode = PQ.pop()
    if currentDist > dist[currentNode]:
        continue
    for neighbor, weight in graph[currentNode]:
        newDist = currentDist + weight
        if newDist < dist[neighbor]:
            dist[neighbor] = newDist
            PQ.push((newDist, neighbor))

Output: dist[]

6. Kruskal’s Algorithm (Minimum Spanning Tree)

Problem: Find the minimum spanning tree of a graph using edge weights.

Greedy Approach:

  • Sort all edges by weight and add edges to the spanning tree if they don’t form a cycle.

Pseudocode:

Input: edges[] (each edge has weight, start, end), number of nodes
Sort edges[] by weight
Initialize disjoint sets for all nodes
MST = []

for edge in edges:
    if edge.start and edge.end are in different sets:
        MST.append(edge)
        Union(edge.start, edge.end)  # Merge sets

Output: MST

7. Job Scheduling Problem

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

Greedy Approach:

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

Pseudocode:

Input: jobs[] (each job has profit and deadline)
Sort jobs[] by profit in descending order
slots[] = [false] * maxDeadline
totalProfit = 0

for job in jobs:
    for slot = min(job.deadline, maxDeadline) to 1:
        if slots[slot] == false:
            slots[slot] = true
            totalProfit += job.profit
            break

Output: totalProfit
Scroll to Top