Why Greedy Works and When It Fails in DSA Typescript - Challenge Your Understanding

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Greedy Coin Change Algorithm

What is the output of the following TypeScript code that uses a greedy approach to make change with coins [25, 10, 5, 1] for amount 37?

DSA Typescript

function greedyCoinChange(coins: number[], amount: number): number[] {
  const result: number[] = [];
  for (const coin of coins) {
    while (amount >= coin) {
      amount -= coin;
      result.push(coin);
    }
  }
  return result;
}

console.log(greedyCoinChange([25, 10, 5, 1], 37));

A [25, 10, 1, 1]

B [25, 5, 5, 1, 1]

C [10, 10, 10, 5, 1, 1]

D [25, 10, 5, 1, 1]

💡 Hint

Think about how the greedy algorithm picks the largest coin first and subtracts it until it can't anymore.

The greedy algorithm picks 25 first (amount left 12), then 10 (amount left 2), then two 1s to make 37. It never picks 5 because 12 < 25 but >= 10, so it picks 10 next.

🧠 Conceptual

intermediate

When Does Greedy Fail for Coin Change?

Given coin denominations [10, 6, 1], which amount below will cause the greedy coin change algorithm to fail to find the minimum number of coins?

A 12

B 15

C 18

D 20

💡 Hint

Try to make 12 with the fewest coins using greedy and compare with the optimal solution.

Greedy picks one 10 coin and two 1 coins (3 coins total) for 12, but the optimal is two 6 coins (2 coins). So greedy fails for 12.

🔧 Debug

advanced

Identify the Bug in Greedy Interval Scheduling

What error does the following TypeScript code produce when trying to select the maximum number of non-overlapping intervals using a greedy approach?

DSA Typescript

interface Interval { start: number; end: number; }

function maxNonOverlapping(intervals: Interval[]): number {
  intervals.sort((a, b) => a.start - b.start);
  let count = 0;
  let lastEnd = -Infinity;
  for (const interval of intervals) {
    if (interval.start >= lastEnd) {
      count++;
      lastEnd = interval.end;
    }
  }
  return count;
}

console.log(maxNonOverlapping([{start:0,end:10},{start:1,end:4},{start:5,end:6}]));

A 2

B TypeError

C 3

D 1

💡 Hint

Check the sorting criteria for intervals in interval scheduling.

The code sorts intervals by start time, but the greedy algorithm for interval scheduling requires sorting by end time. This causes suboptimal selection and count 1 instead of 2.

🚀 Application

advanced

Greedy Algorithm for Activity Selection Output

Given activities with start and end times: [(1,4), (3,5), (0,6), (5,7), (8,9), (5,9)], what is the output list of selected activities using the greedy algorithm that picks the earliest finishing activity first?

DSA Typescript

interface Activity { start: number; end: number; }

function selectActivities(activities: Activity[]): Activity[] {
  activities.sort((a, b) => a.end - b.end);
  const selected: Activity[] = [];
  let lastEnd = -Infinity;
  for (const activity of activities) {
    if (activity.start >= lastEnd) {
      selected.push(activity);
      lastEnd = activity.end;
    }
  }
  return selected;
}

console.log(selectActivities([{start:1,end:4},{start:3,end:5},{start:0,end:6},{start:5,end:7},{start:8,end:9},{start:5,end:9}]));

A [(1,4), (3,5), (5,7), (8,9)]

B [(1,4), (5,7), (8,9)]

C [(0,6), (5,9)]

D [(3,5), (5,7), (8,9)]

💡 Hint

Sort activities by their end time and pick those that start after the last selected ends.

The greedy algorithm picks (1,4), then (5,7), then (8,9) as they don't overlap and finish earliest.

🧠 Conceptual

expert

Why Greedy Algorithm Fails for 0/1 Knapsack Problem

Why does the greedy algorithm that picks items by highest value-to-weight ratio fail to always find the optimal solution for the 0/1 Knapsack problem?

A Because it does not consider the total weight limit and may pick items that don't fit together optimally

B Because it always picks the smallest items first

C Because it only works when items can be broken into fractions

D Because it sorts items by weight instead of value

💡 Hint

Think about the difference between fractional and 0/1 knapsack problems.

Greedy works for fractional knapsack where items can be split, but fails for 0/1 knapsack because picking by ratio may exclude better combinations.