Greedy Algorithms: When, Why, and How They Shine!

Let's explore the world of Greedy Algorithms: what they are, when they work best, and when they fall short!

Hey there, amazing coders 👨‍💻! Today we’re diving into the world of Greedy Algorithms, a magical land of quick decisions, instant gratification, and minimizing regret. Imagine a goblin who grabs the shiniest coins without looking further ahead. Sometimes, his strategy works out great... and sometimes, he ends up missing the gold pile entirely! So how do we know when a Greedy Algorithm is a “winning strategy”? Let’s find out!

---

🧙‍♂️ What’s a Greedy Algorithm?

A Greedy Algorithm is all about making local, optimal choices at each step, without worrying about what happens next. It’s like grabbing the shiniest thing you see at each moment and hoping this path will lead you to the treasure!

In technical terms, a Greedy Algorithm is a way of solving problems by:

1. Making the best possible choice at each step.

2. Not thinking too far ahead, just focusing on what looks best at that exact moment.

3. Hoping that all those good steps add up to a good overall solution.

Example:

Imagine you’re shopping, and you only have $50. You see a few cool items on sale. Instead of carefully calculating how many items you can buy in total with $50, you just pick the biggest discount each time until you run out of money. You hope that, by choosing the biggest discounts as you go, you’ll get the best value out of your $50.

But here’s the twist: Greedy Algorithms aren’t always perfect! They only work well when they lead to the best solution naturally.

---

💎When Do Greedy Algorithms Work Best?

Greedy algorithms work in two cases:

1. The Problem Has the Greedy Choice Property

If every local, greedy choice leads to a global solution, then greedy is your friend. For example, if we’re trying to find the minimum number of coins to make a certain amount, choosing the highest-value coin every time will give the best solution!

Example:

Say you want to pay exactly $30 using as few coins as possible. You have coins worth $1, $5, $10, and $25. Here’s how a Greedy Algorithm would approach this:

1. Pick the biggest coin (the $25) because it gets you closest to $30 right away.

2. Subtract that amount from $30 (now you’re down to $5).

3. For the remaining $5, pick another $5 coin (because that’s the biggest coin left that still works).

// Time complexity => O(n*logn + n*k)
function minimumCoins(amount, coins) {
    let count = 0;
    // Sort coins from largest to smallest O(nlogn)
    coins.sort((a, b) => b - a);
    // looping through the coins O(n)
    for (let coin of coins) {
        // using the coins unless it's not usefull anymore 
        // O(k) where k is the number of one coin usage
        while (amount >= coin) {
            amount -= coin;
            // counting usage time
            count++;
        }
    }
    return count;
}

console.log(minimumCoins(30, [1, 5, 10, 25])); // Output: 2 (one 25, one 5)

Result: You used two coins ($25 and $5), which is the fewest coins needed to make $30. Greedy works great here because: choosing the largest coin each time also results in the smallest total number of coins.

2. The Problem Structure Favors a Step-by-Step Solution 🚶‍♂️

When each step directly contributes to the best solution, greedy works well. Imagine you have a list of tasks you want to complete today, and each task has a start and end time 🕒. Your goal is to complete as many tasks as possible without any overlap.

The Greedy Approach: Always pick the task that finishes the earliest. This way, you maximize the amount of time left to complete the next task.

Example:

Let’s say you have these tasks:

• Task A: 9 am to 10 am

• Task B: 9:30 am to 11 am

• Task C: 10 am to 11 am

• Task D: 11 am to 12 pm

Now let’s use a Greedy Algorithm to choose tasks:

1. Sort tasks by their finish time. So, after sorting:

   • Task A: 9 am - 10 am

   • Task C: 10 am - 11 am

   • Task B: 9:30 am - 11 am

   • Task D: 11 am - 12 pm

2. Choose the earliest-ending task first. We start with Task A (9 am to 10 am).

3. Pick the next task that starts after Task A finish. Task C (10 am to 11 am) fits, so we pick it.

4. Next, pick the next task that starts after Task C finishes. That would be Task D (11 am to 12 pm).

function maxTasks(tasks) {
    // Sort tasks by their finish times
    tasks.sort((a, b) => a[1] - b[1]);

    let count = 0;
    let lastFinishTime = 0;

    for (let [start, finish] of tasks) {
        if (start >= lastFinishTime) { // Can take this task
            count++;
            lastFinishTime = finish; // Update last finished time
        }
    }
    return count;
}

// Each task is represented as [startTime, finishTime]
const tasks = [
    [9, 10], // Task A
    [9.5, 11], // Task B
    [10, 11], // Task C
    [11, 12]  // Task D
];

console.log(maxTasks(tasks)); // Output: 3 (Tasks A, C, and D)

Result: We were able to complete three tasks: Task A, Task C, and Task D. Notice that Task B couldn’t fit without overlapping, so we skipped it.

In this example, the greedy choice (earliest finish time) at each step helps maximize the total number of tasks completed. By choosing the task that finishes first, you’re always in the best position to pick the next task without overlap, leading to the best possible outcome!

---

🚫When Greedy Doesn't Work ?

Imagine you’re trying to split a cake 🎂 fairly between friends, each wanting a big slice. You might cut the biggest slice possible for the first person, then realize later that the rest of the cake can’t be split equally between everyone else! Here, each “greedy” choice (giving the biggest slice) doesn’t lead to the best outcome for everybody!

In cases like this, where you need balance, a Greedy Algorithm won’t work ! Because choices made early on, impact drastically future choices!

---

💯Key Points to Remember:

1. Greedy Algorithms are fast but work only if each step’s best choice adds up to the best solution.

2. They work best in problems where each small choice leads naturally to the best overall result (like the coin example).

3. They don’t work well if choices at each step affect future choices, like splitting something into equal parts.

Greedy Algorithms are great when they work but fail if the problem requires planning.

I hope this article gives you a clear understanding of Greedy Algorithms: what they are, when they work best, and when not!

See you in the next adventure, thelaaaaw👋

🔔 Don't forget to subscribe to my blog and YouTube channel to stay updated with all the latest content!