Why Greedy Works and When It Fails in DSA Javascript - See It Work

Why Greedy Works and When It Fails

📖 Scenario: Imagine you are organizing a small event and need to select snacks within a budget. You want to pick snacks that cost the least first to get the most variety. This is a simple example of a greedy approach. But sometimes, picking the cheapest first doesn't give the best overall result. Let's explore why greedy works in some cases and fails in others.

🎯 Goal: You will create a list of snack prices, set a budget, use a greedy method to pick snacks starting from the cheapest, and then see the final selection. This will help you understand when greedy choices lead to good or bad results.

📋 What You'll Learn

Create an array called snackPrices with exact values: 2, 5, 1, 3, 4

Create a variable called budget and set it to 7

Use a greedy approach to select snacks starting from the cheapest until the budget is reached or exceeded

Print the final list of selected snack prices

💡 Why This Matters

🌍 Real World

Greedy algorithms are used in many real-life situations like scheduling tasks, making change with coins, or selecting projects within a budget.

💼 Career

Understanding when greedy algorithms work or fail helps in software development, especially in optimization problems and algorithm design.

1

Create the snack prices list

Create an array called snackPrices with these exact values: 2, 5, 1, 3, 4

DSA Javascript

// Create the snackPrices array with the given values
// Your code here

Hint

Use square brackets [] to create an array and separate values with commas.

2

Set the budget

Create a variable called budget and set it to 7

DSA Javascript

const snackPrices = [2, 5, 1, 3, 4];
// Create the budget variable and set it to 7
// Your code here

Hint

Use const to create a variable and assign the number 7.

3

Select snacks using greedy approach

Create an empty array called selectedSnacks. Sort snackPrices in ascending order. Use a for loop with variable price to go through the sorted prices. Add price to selectedSnacks only if the sum of selected snacks plus price does not exceed budget. Keep track of the total cost in a variable called totalCost.

DSA Javascript

const snackPrices = [2, 5, 1, 3, 4];
const budget = 7;
// Create selectedSnacks array and totalCost variable
// Sort snackPrices
// Use for loop to select snacks greedily
// Your code here

Hint

Use slice() to copy the array before sorting to avoid changing the original. Use sort((a, b) => a - b) to sort numbers ascending. Use a for...of loop to iterate.

4

Print the selected snacks

Use console.log to print the selectedSnacks array

DSA Javascript

const snackPrices = [2, 5, 1, 3, 4];
const budget = 7;
const selectedSnacks = [];
let totalCost = 0;
const sortedPrices = snackPrices.slice().sort((a, b) => a - b);
for (const price of sortedPrices) {
    if (totalCost + price <= budget) {
        selectedSnacks.push(price);
        totalCost += price;
    } else {
        break;
    }
}
// Print the selectedSnacks array
// Your code here

Hint

Use console.log(selectedSnacks) to display the array.

Practice

1. What is the main reason a greedy algorithm works correctly for some problems?

easy

A. Because it makes the best choice at each step hoping for a global optimum

B. Because it tries all possible solutions before choosing one

C. Because it uses recursion to explore all paths

D. Because it sorts the input data first

Solution

1. Step 1: Understand greedy choice property

   A greedy algorithm picks the best option at each step without reconsidering previous choices.

2. Step 2: Connect greedy choice to global optimum

   This local best choice leads to a global optimum only if the problem has the greedy choice property.

3. Final Answer:

   Because it makes the best choice at each step hoping for a global optimum -> Option A

4. Quick Check:

   Greedy choice property = best local choice [OK]

Hint: Greedy picks best local choice, not all solutions [OK]

Common Mistakes:

• Thinking greedy tries all solutions
• Confusing greedy with recursion
• Assuming sorting always solves the problem

2. Which of the following is the correct syntax to start a greedy algorithm loop in JavaScript to process an array arr?

easy

A. for (const item in arr) {}

B. while (arr.length) {}

C. for (let i = 0; i < arr.length; i++) {}

D. arr.forEach(i => {})

Solution

1. Step 1: Identify standard loop for arrays

   The standard way to loop over array elements by index is for (let i = 0; i < arr.length; i++).

2. Step 2: Check other options

   while (arr.length) loops infinitely unless modified; for...in loops keys, not values; forEach is valid but less common for greedy step control.

3. Final Answer:

   for (let i = 0; i < arr.length; i++) {} -> Option C

4. Quick Check:

   Standard for loop = for (let i = 0; i < arr.length; i++) {} [OK]

Hint: Use for loop with index for greedy steps [OK]

Common Mistakes:

• Using for...in for arrays (loops keys)
• Using while without proper exit
• Confusing forEach with for loop syntax

3. What will be the output of the following JavaScript code that tries to select intervals greedily by earliest finish time?

const intervals = [[1,4],[2,3],[3,5]];
intervals.sort((a,b) => a[1] - b[1]);
const result = [];
let lastEnd = 0;
for (const [start, end] of intervals) {
  if (start >= lastEnd) {
    result.push([start, end]);
    lastEnd = end;
  }
}
console.log(result);

medium

A. [[1,4]]

B. [[1,4],[3,5]]

C. [[2,3]]

D. [[2,3],[3,5]]

Solution

1. Step 1: Sort intervals by finish time

   Sorted intervals: [[2,3],[1,4],[3,5]] because 3 < 4 < 5.

2. Step 2: Select intervals greedily

   Start with lastEnd=0. Check [2,3]: 2 >= 0, select it, lastEnd=3. Next [1,4]: 1 < 3, skip. Next [3,5]: 3 >= 3, select it, lastEnd=5.

3. Final Answer:

   [[2,3],[3,5]] -> Option D

4. Quick Check:

   Greedy interval selection = [[2,3],[3,5]] [OK]

Hint: Sort by finish time, pick non-overlapping intervals [OK]

Common Mistakes:

• Not sorting intervals by finish time
• Selecting overlapping intervals
• Updating lastEnd incorrectly

4. The following code tries to find the minimum number of coins for a given amount using greedy approach with coins [1, 3, 4]. Why does it fail for amount = 6?

const coins = [4, 3, 1];
let amount = 6;
let count = 0;
for (const coin of coins) {
  while (amount >= coin) {
    amount -= coin;
    count++;
  }
}
console.log(count);

medium

A. It outputs 3 but the minimum coins needed is 2

B. It outputs 2 which is correct

C. It causes an infinite loop

D. It outputs 6 which is incorrect

Solution

1. Step 1: Trace greedy coin selection

   Greedy picks 4 once (amount=2), then picks 1 twice (amount=0), total 3 coins.

2. Step 2: Check optimal solution

   Optimal is 2 coins: 3 + 3 = 6, fewer than greedy's 3 coins.

3. Final Answer:

   It outputs 3 but the minimum coins needed is 2 -> Option A

4. Quick Check:

   Greedy fails for coin sets without canonical property [OK]

Hint: Greedy may fail if coin set is non-standard [OK]

Common Mistakes:

• Assuming greedy always gives minimum coins
• Not checking smaller coin combinations
• Ignoring coin order importance

5. You want to schedule the maximum number of non-overlapping meetings from the list [[0, 30], [5, 10], [15, 20]]. Which approach correctly applies greedy algorithm and what is the maximum number of meetings?

hard

A. Sort by start time, pick earliest start; maximum meetings = 2

B. Sort by finish time, pick earliest finish; maximum meetings = 2

C. Sort by duration, pick shortest; maximum meetings = 3

D. Sort by finish time, pick earliest finish; maximum meetings = 3

Solution

1. Step 1: Sort meetings by finish time

   Sorted: [5,10], [15,20], [0,30] (finish times 10, 20, 30).

2. Step 2: Select meetings greedily

   Pick [5,10], next [15,20] starts after 10, pick it; [0,30] overlaps, skip.

3. Final Answer:

   Sort by finish time, pick earliest finish; maximum meetings = 2 -> Option B

4. Quick Check:

   Greedy by finish time = 2 meetings [OK]

Hint: Sort by finish time for max non-overlapping meetings [OK]

Common Mistakes:

• Sorting by start time instead of finish time
• Assuming shortest duration always works
• Counting overlapping meetings