Skip to main content

Greedy Algorithms

Greedy algorithms make locally optimal choices at each step, hoping to find a global optimum.

What are Greedy Algorithms?​

A greedy algorithm makes the locally optimal choice at each step, hoping that these local choices will lead to a globally optimal solution.

When to Use?​

  • When local optimal choices lead to global optimal solution
  • When you need to find an approximate solution quickly
  • Problems involving optimization

Common Applications​

  • Minimum Spanning Tree (Kruskal's, Prim's)
  • Dijkstra's Shortest Path
  • Huffman Coding
  • Activity Selection
  • Coin Change (with certain constraints)

Example Problems​

1. Coin Change Problem​

Problem Description​

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

Example​

Input: coins = [1, 5, 10, 25], amount = 67
Output: 6
Explanation: 25 + 25 + 10 + 5 + 1 + 1 = 67 (6 coins)

Solution​

function minCoins(coins, amount) {
	// Sort coins in descending order
	coins.sort((a, b) => b - a);

	let totalCoins = 0;
	let remaining = amount;
	let result = [];

	for (let coin of coins) {
		while (remaining >= coin) {
			remaining -= coin;
			totalCoins++;
			result.push(coin);
		}
	}

	return {
		numberOfCoins: totalCoins,
		coinsUsed: result,
		amount: amount,
	};
}

Time Complexity​

  • Time: O(n * amount) where n is the number of coin denominations
  • Space: O(1)

2. Activity Selection Problem​

Problem Description​

Given a set of activities with start and finish times, find the maximum number of activities that can be performed by a single person, assuming they can only work on one activity at a time.

Example​

Input:
start  = [1, 3, 0, 5, 8, 5]
finish = [2, 4, 6, 7, 9, 9]
Output: 4
Explanation: Activities (1,2), (3,4), (5,7), (8,9) can be selected

Solution​

function activitySelection(start, finish) {
	// Create activities array with indices
	let activities = start.map((s, i) => ({
		index: i,
		start: s,
		finish: finish[i],
	}));

	// Sort by finish time
	activities.sort((a, b) => a.finish - b.finish);

	let selected = [activities[0]];
	let lastSelected = activities[0];

	for (let i = 1; i < activities.length; i++) {
		if (activities[i].start >= lastSelected.finish) {
			selected.push(activities[i]);
			lastSelected = activities[i];
		}
	}

	return {
		count: selected.length,
		activities: selected.map((a) => a.index),
	};
}

Time Complexity​

  • Time: O(n log n) due to sorting
  • Space: O(n)

Practice Problems​

To master greedy algorithms, try solving these problems:

  1. Fractional Knapsack
  2. Job Sequencing with Deadlines
  3. Huffman Coding
  4. Minimum Platforms
  5. Maximum Meetings in One Room

Common Greedy Strategies​

  1. Sort First

    • Sort input based on some criteria
    • Make decisions in sorted order

  2. Take Maximum/Minimum

    • Choose the largest/smallest available option
    • Useful in optimization problems

  3. Interval Scheduling

    • Sort by end time
    • Select non-overlapping intervals

Tips for Solving Greedy Problems​

  1. Verify that greedy approach works
  2. Identify the local optimal choice
  3. Prove correctness if possible
  4. Consider edge cases
  5. Look for sorting opportunities

When Greedy Might Fail​

  1. 0/1 Knapsack Problem

    • Greedy doesn't work because we can't take fractions
    • Requires dynamic programming

  2. Traveling Salesman Problem

    • Local optimal choices don't lead to global optimum
    • Requires other approaches

Additional Resources​

Last updated on