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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Greedy Coin Change Algorithm

What is the output of the following C# code that uses a greedy approach to make change with coins of denominations 1, 5, and 10 for the amount 18?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        int amount = 18;
        int[] coins = {10, 5, 1};
        List<int> result = new List<int>();
        foreach (int coin in coins) {
            while (amount >= coin) {
                amount -= coin;
                result.Add(coin);
            }
        }
        Console.WriteLine(string.Join(", ", result));
    }
}

A 10, 5, 1, 1, 1

B 10, 5, 5

C 5, 5, 5, 1, 1, 1

D 10, 1, 1, 1, 1, 1, 1, 1, 1

💡 Hint

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

The greedy algorithm picks the largest coin (10) once, then the next largest (5) once, then uses 1 coins to complete the amount. So the output is 10, 5, 1, 1, 1.

🧠 Conceptual

intermediate

Why Greedy Fails for Certain Coin Systems

Why does the greedy algorithm fail to find the minimum number of coins for the amount 6 when the coin denominations are 1, 3, and 4?

A Because the greedy algorithm always picks the smallest coin first, it ends up with too many coins.

B Because the greedy algorithm picks the largest coin first, it chooses 4 and then two 1s, totaling 3 coins, but the optimal is two 3s.

C Because the greedy algorithm sorts coins in ascending order and picks the smallest first, it misses larger coins.

D Because the greedy algorithm uses dynamic programming internally, it sometimes picks suboptimal coins.

💡 Hint

Consider how the greedy algorithm picks coins and compare with the optimal solution.

The greedy algorithm picks the largest coin less than or equal to the remaining amount. For 6, it picks 4 first, then two 1s, totaling 3 coins. But the optimal solution is two 3s, totaling 2 coins.

🔧 Debug

advanced

Identify the Error in Greedy Interval Scheduling Code

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

DSA C#

using System;
using System.Collections.Generic;

class Interval {
    public int start, end;
    public Interval(int s, int e) { start = s; end = e; }
}

class Program {
    static void Main() {
        List<Interval> intervals = new List<Interval> {
            new Interval(1, 3),
            new Interval(2, 5),
            new Interval(4, 7)
        };
        intervals.Sort((a, b) => a.start - b.start);
        List<Interval> selected = new List<Interval>();
        int lastEnd = 0;
        foreach (var interval in intervals) {
            if (interval.start >= lastEnd) {
                selected.Add(interval);
                lastEnd = interval.end;
            }
        }
        Console.WriteLine(selected.Count);
    }
}

A The code compiles and runs, outputting 2

B The code compiles but outputs 3, which is incorrect

C The code throws a NullReferenceException at runtime

D The code fails to compile due to a syntax error in the Sort lambda

💡 Hint

Check how intervals are sorted and how selection is done.

The code sorts intervals by start time and selects intervals greedily if they don't overlap. This approach works but is not optimal for interval scheduling. However, the code runs and outputs 2, which is the number of non-overlapping intervals selected.

❓ Predict Output

advanced

Output of Greedy Interval Scheduling with End-Time Sorting

What is the output of the following C# code that selects the maximum number of non-overlapping intervals by sorting intervals by their end time?

DSA C#

using System;
using System.Collections.Generic;

class Interval {
    public int start, end;
    public Interval(int s, int e) { start = s; end = e; }
}

class Program {
    static void Main() {
        List<Interval> intervals = new List<Interval> {
            new Interval(1, 3),
            new Interval(2, 5),
            new Interval(4, 7)
        };
        intervals.Sort((a, b) => a.end - b.end);
        List<Interval> selected = new List<Interval>();
        int lastEnd = 0;
        foreach (var interval in intervals) {
            if (interval.start >= lastEnd) {
                selected.Add(interval);
                lastEnd = interval.end;
            }
        }
        Console.WriteLine(selected.Count);
    }
}

A 3

B 1

C 2

D 0

💡 Hint

Sorting by end time allows selecting more intervals.

Sorting intervals by their end time and selecting intervals greedily ensures the maximum number of non-overlapping intervals are chosen. Here, it selects (1,3) and (4,7), outputting 2.

🧠 Conceptual

expert

When Does Greedy Algorithm Guarantee Optimal Solution?

Which condition below guarantees that a greedy algorithm will always produce an optimal solution for a problem?

A The problem has no constraints and unlimited resources.

B The problem has overlapping subproblems and uses memoization.

C The problem can be solved by brute force in polynomial time.

D The problem exhibits the greedy-choice property and optimal substructure.

💡 Hint

Think about the two key properties that make greedy algorithms work.

A greedy algorithm works optimally when the problem has the greedy-choice property (local optimal choices lead to global optimum) and optimal substructure (optimal solution contains optimal solutions to subproblems).

Practice

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

easy

A. Because it sorts the input data before processing

B. Because it tries all possible solutions and picks the best

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

D. Because it uses recursion to explore all paths

Solution

1. Step 1: Understand greedy choice property

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

2. Step 2: Connect local choices to global optimum

   For some problems, these local best choices lead to the overall best solution, which is why greedy works.

3. Final Answer:

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

4. Quick Check:

   Greedy = best local choice each step [OK]

Hint: Greedy picks best now, hoping for best overall [OK]

Common Mistakes:

• Thinking greedy tries all solutions
• Confusing greedy with backtracking
• Assuming sorting always means greedy

2. Which of the following is the correct syntax to start a greedy algorithm loop in C# to process a sorted array named arr?

easy

A. foreach (int i in arr.Length)

B. for (int i = 0; i < arr.Length; i++)

C. while (i <= arr.Length)

D. for (int i = 1; i <= arr.Length; i++)

Solution

1. Step 1: Identify correct for loop syntax in C#

   The standard for loop iterates from 0 to less than array length using i < arr.Length.

2. Step 2: Check each option for syntax correctness

   for (int i = 0; i < arr.Length; i++) uses correct syntax; B uses foreach incorrectly; C uses while with undefined i; D uses 1-based index which is off by one.

3. Final Answer:

   for (int i = 0; i < arr.Length; i++) -> Option B

4. Quick Check:

   for loop with i from 0 to length-1 [OK]

Hint: Use for loop from 0 to less than length [OK]

Common Mistakes:

• Using foreach with arr.Length instead of arr
• Starting loop at 1 instead of 0
• Using while without initializing i

3. Consider the following C# code that tries to select the maximum number of non-overlapping intervals using a greedy approach:

var intervals = new List<(int start, int end)> { (1,3), (2,5), (4,7), (6,9) };
intervals.Sort((a,b) => a.end.CompareTo(b.end));
var count = 0;
int lastEnd = int.MinValue;
foreach (var interval in intervals) {
  if (interval.start >= lastEnd) {
    count++;
    lastEnd = interval.end;
  }
}
Console.WriteLine(count);

What is the output of this code?

medium

A. 2

B. 1

C. 4

D. 3

Solution

1. Step 1: Sort intervals by end time

   Sorted intervals: (1,3), (2,5), (4,7), (6,9)

2. Step 2: Select intervals greedily

   Pick (1,3) first (count=1, lastEnd=3). Next (2,5) starts before 3, skip. Next (4,7) starts after 3, pick (count=2, lastEnd=7). Next (6,9) starts after 7, pick (count=3, lastEnd=9).

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Greedy interval selection count = 3 [OK]

Hint: Sort by end, pick intervals starting after last end [OK]

Common Mistakes:

• Counting overlapping intervals
• Not sorting by end time
• Updating lastEnd incorrectly

4. The following C# code tries to solve the coin change problem using a greedy approach but sometimes fails. What is the bug?

int[] coins = {1, 3, 4};
int amount = 6;
int count = 0;
for (int i = coins.Length - 1; i >= 0; i--) {
  while (amount >= coins[i]) {
    amount -= coins[i];
    count++;
  }
}
Console.WriteLine(count);

medium

A. Greedy fails because coin denominations are not standard, so it misses optimal solution

B. The loop should start from 0, not from coins.Length - 1

C. The while condition should be amount > coins[i], not >=

D. The count variable is not initialized to zero

Solution

1. Step 1: Understand greedy coin change approach

   Greedy picks largest coin first repeatedly until amount is less, then smaller coins.

2. Step 2: Check coin denominations and optimality

   With coins {1,3,4} and amount 6, greedy picks 4 + 1 + 1 = 3 coins, but optimal is 3 + 3 = 2 coins.

3. Final Answer:

   Greedy fails because coin denominations are not standard, so it misses optimal solution -> Option A

4. Quick Check:

   Non-standard coins break greedy optimality [OK]

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

Common Mistakes:

• Thinking loop direction causes failure
• Confusing while condition with off-by-one
• Ignoring coin denomination impact

5. You want to schedule the maximum number of tasks without overlap. Each task has a start and end time. Which approach guarantees the optimal solution and why?

Options:
A) Sort tasks by start time and pick earliest starting tasks
B) Sort tasks by duration and pick shortest tasks first
C) Sort tasks by end time and pick tasks finishing earliest first
D) Pick tasks randomly and check for overlaps

hard

A. Sort tasks by end time and pick tasks finishing earliest first

B. Sort tasks by duration and pick shortest tasks first

C. Sort tasks by start time and pick earliest starting tasks

D. Pick tasks randomly and check for overlaps

Solution

1. Step 1: Understand the interval scheduling problem

   The goal is to select maximum non-overlapping tasks.

2. Step 2: Identify greedy strategy that works

   Sorting by end time and picking earliest finishing tasks ensures maximum room for future tasks, proven optimal.

3. Step 3: Evaluate other options

   Sorting by start time or duration can lead to suboptimal selections; random picks are unreliable.

4. Final Answer:

   Sort tasks by end time and pick tasks finishing earliest first -> Option A

5. Quick Check:

   Earliest finish time greedy = optimal schedule [OK]

Hint: Pick tasks finishing earliest first for max schedule [OK]

Common Mistakes:

• Choosing earliest start time instead of end time
• Picking shortest duration tasks ignoring overlaps
• Assuming random picks can be optimal