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 for 30 cents with coin denominations 25, 10, and 1?

DSA C

#include <stdio.h>

int main() {
    int coins[] = {25, 10, 1};
    int amount = 30;
    int count[3] = {0};

    for (int i = 0; i < 3; i++) {
        while (amount >= coins[i]) {
            amount -= coins[i];
            count[i]++;
        }
    }

    printf("Coins used: 25c=%d, 10c=%d, 1c=%d\n", count[0], count[1], count[2]);
    return 0;
}

A Coins used: 25c=1, 10c=0, 1c=0

B Coins used: 25c=0, 10c=3, 1c=0

C Coins used: 25c=1, 10c=0, 1c=5

D Coins used: 25c=0, 10c=2, 1c=10

💡 Hint

Think about how the greedy algorithm picks the largest coin first and then moves to smaller coins.

The greedy algorithm picks one 25-cent coin first (amount reduces from 30 to 5), then cannot pick any 10-cent coin because 5 < 10, so it picks five 1-cent coins. So the output is 25c=1, 10c=0, 1c=5.

🧠 Conceptual

intermediate

When Does Greedy Fail in Coin Change?

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

A Because the greedy algorithm picks the largest coin first, it chooses 4, then two 1-cent coins, totaling 3 coins, but the optimal is two 3-cent coins, which is 2 coins total.

B Because the greedy algorithm picks the largest coin first, it chooses 4, then two 1-cent coins, totaling 3 coins, but the optimal is one 3-cent coin and three 1-cent coins, which is 4 coins total.

C Because the greedy algorithm picks the largest coin first, it chooses 3, then 3, totaling 2 coins, but the optimal is something else.

D The greedy algorithm actually finds the optimal solution here.

💡 Hint

Check how many coins the greedy picks versus the optimal solution with these denominations.

Greedy picks one 4-cent + two 1-cent coins = 3 coins. The optimal is two 3-cent coins = 2 coins.

❓ Predict Output

advanced

Output of Interval Scheduling Greedy Algorithm

What is the output of the following C code that selects the maximum number of non-overlapping intervals using a greedy approach?

DSA C

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int start;
    int end;
} Interval;

int compare(const void *a, const void *b) {
    Interval *i1 = (Interval *)a;
    Interval *i2 = (Interval *)b;
    return i1->end - i2->end;
}

int main() {
    Interval intervals[] = {{1,4}, {3,5}, {0,6}, {5,7}, {8,9}, {5,9}};
    int n = sizeof(intervals)/sizeof(intervals[0]);

    qsort(intervals, n, sizeof(Interval), compare);

    int count = 1;
    int last_end = intervals[0].end;

    for (int i = 1; i < n; i++) {
        if (intervals[i].start >= last_end) {
            count++;
            last_end = intervals[i].end;
        }
    }

    printf("Maximum non-overlapping intervals: %d\n", count);
    return 0;
}

A Maximum non-overlapping intervals: 5

B Maximum non-overlapping intervals: 3

C Maximum non-overlapping intervals: 4

D Maximum non-overlapping intervals: 2

💡 Hint

The greedy algorithm sorts intervals by end time and picks intervals that start after the last chosen interval ends.

Sorted by end time: {1,4}, {3,5}, {0,6}, {5,7}, {8,9}, {5,9}. Picks {1,4} (last_end=4), skips next two, picks {5,7} (5>=4, last_end=7), picks {8,9} (8>=7), skips {5,9}. Total: 3.

🔧 Debug

advanced

Identify the Error in Greedy Activity Selector

What error does the following C code produce when trying to select maximum activities using a greedy approach?

DSA C

#include <stdio.h>

int main() {
    int start[] = {1, 3, 0, 4, 8, 5};
    int finish[] = {2, 4, 6, 7, 9, 9};
    int n = 6;
    int count = 1;
    int last_finish = finish[0];

    for (int i = 1; i < n; i++) {
        if (start[i] > last_finish) {
            count++;
            last_finish = finish[i];
        }
    }

    printf("Number of activities selected: %d\n", count);
    return 0;
}

A The code outputs: Number of activities selected: 1

B The code outputs: Number of activities selected: 4

C The code outputs: Number of activities selected: 2

D The code outputs: Number of activities selected: 3

💡 Hint

Check the condition for selecting activities and the sorting of activities by finish time.

The code outputs 3 because it does not sort by finish time and uses strict '>' (skips activity 3 where start[3]=4 == last_finish=4 after activity 1). Optimal is 4 activities. Fix: sort by finish time ascending and use '>='.

🚀 Application

expert

Greedy Algorithm Failure in Job Scheduling with Deadlines

Given jobs with deadlines and profits, which greedy approach fails to maximize profit? Jobs: {Job1: deadline=2, profit=100}, {Job2: deadline=1, profit=19}, {Job3: deadline=2, profit=27}, {Job4: deadline=1, profit=25}, {Job5: deadline=3, profit=15}. Which option shows the incorrect greedy approach and its resulting profit?

A Scheduling jobs in ascending order of deadline and assigning latest available slot results in total profit 134.

B Scheduling jobs in ascending order of profit and assigning earliest available slot results in total profit 61.

C Scheduling jobs in descending order of profit and assigning latest available slot results in total profit 142.

D Scheduling jobs in descending order of profit and assigning earliest available slot results in total profit 142.

💡 Hint

The correct greedy approach schedules jobs by descending profit and assigns the latest available slot before deadline.

Scheduling by ascending deadline and latest slot is incorrect and suboptimal (134 < 142). Correct: descending profit + latest slot = 142 (Job1 slot2, Job3 slot1, Job5 slot3).

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 and picks the best one

C. Because it uses recursion to explore all options

D. Because it sorts the input data before processing

Solution

1. Step 1: Understand greedy choice property

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

2. Step 2: Connect greedy choice to global optimum

   For some problems, making the best local choice at each step leads to the best overall solution.

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 = Because it makes the best choice at each step hoping for a global optimum [OK]

Hint: Greedy picks best local choice hoping for best overall [OK]

Common Mistakes:

• Thinking greedy tries all solutions
• Confusing greedy with recursion or backtracking
• Assuming sorting alone makes greedy correct

2. Which of the following is the correct syntax to pick the next item greedily from a sorted array arr in C?

easy

A. int next = arr[--i];

B. int next = arr[i]; i++;

C. int next = arr[++i];

D. int next = arr[i]; i--;

Solution

1. Step 1: Understand post-increment vs pre-increment

   Post-increment i++ returns current value then increments; pre-increment ++i increments then returns.

2. Step 2: Choose syntax that picks current item then moves forward

   int next = arr[i]; i++; picks current element and then increments index for next pick.

3. Final Answer:

   int next = arr[i]; i++; -> Option B

4. Quick Check:

   Pick current then increment index = int next = arr[i]; i++; [OK]

Hint: Pick current element then increment index separately [OK]

Common Mistakes:

• Using pre-increment which skips first element
• Decrementing index instead of incrementing
• Confusing post-increment inside array index

3. Consider the following C code that tries to select intervals greedily by earliest finish time:

typedef struct {
  int start;
  int end;
} Interval;

int main() {
  Interval arr[] = {{1,4}, {3,5}, {0,6}, {5,7}, {8,9}};
  int n = 5, count = 0, last_end = 0;
  for (int i = 0; i < n; i++) {
    if (arr[i].start >= last_end) {
      count++;
      last_end = arr[i].end;
    }
  }
  printf("%d\n", count);
  return 0;
}

What is the output?

medium

A. 3

B. 4

C. 5

D. 2

Solution

1. Step 1: Trace interval selection without sorting

   Intervals are checked in given order: {1,4}, {3,5}, {0,6}, {5,7}, {8,9}. - Pick {1,4} (start 1 >= 0), count=1, last_end=4 - {3,5} start 3 < 4 skip - {0,6} start 0 < 4 skip - {5,7} start 5 >= 4 pick, count=2, last_end=7 - {8,9} start 8 >= 7 pick, count=3, last_end=9

2. Step 2: Check if output matches options

   Count is 3, but 2 is 2, so check carefully: initial last_end=0, first interval start=1 >=0 pick count=1 Second interval start=3 < 4 skip Third start=0 < 4 skip Fourth start=5 >=4 pick count=2 Fifth start=8 >=7 pick count=3 Output is 3

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Greedy without sorting picks 3 intervals [OK]

Hint: Without sorting, greedy may pick fewer intervals [OK]

Common Mistakes:

• Assuming intervals are sorted by end time
• Counting all intervals without checking overlap
• Confusing start and end comparisons

4. The following code tries to solve the coin change problem greedily by picking the largest coin first. What is the bug?

int coins[] = {25, 10, 5, 1};
int amount = 30, count = 0;
for (int i = 0; i < 4; i++) {
  while (amount >= coins[i]) {
    amount -= coins[i];
    count++;
  }
}
printf("%d\n", count);

medium

A. The coin array is not sorted in descending order

B. The amount variable should be reset inside the loop

C. Greedy fails for some amounts, so this may not give minimum coins

D. The loop should run backwards from smallest coin

Solution

1. Step 1: Understand greedy coin change approach

   The code picks largest coin repeatedly until amount is reduced, then moves to smaller coins.

2. Step 2: Identify when greedy fails

   Greedy works for US coins but fails for some coin sets or amounts (e.g., coins {10,6,1} and amount 12). Here, greedy may not minimize coin count.

3. Final Answer:

   Greedy fails for some amounts, so this may not give minimum coins -> Option C

4. Quick Check:

   Greedy coin change can fail minimum count [OK]

Hint: Greedy coin change not always minimal [OK]

Common Mistakes:

• Thinking sorting fixes greedy failure
• Changing loop direction without reason
• Resetting amount inside loop incorrectly

5. You want to schedule the maximum number of non-overlapping meetings from this list:

struct Meeting { int start; int end; };
Meeting meetings[] = {{0,10}, {1,3}, {4,5}};
int n = 3;

Which approach guarantees the maximum meetings scheduled and why does a greedy approach based on earliest start time fail here?

hard

A. Sort by longest duration and pick greedily; shortest duration fails because it picks too many meetings

B. Sort by earliest start time and pick greedily; earliest finish time fails because it ignores start times

C. Pick meetings randomly; sorting is not needed for maximum scheduling

D. Sort by earliest finish time and pick greedily; earliest start time fails because it may pick long meetings blocking others

Solution

1. Step 1: Identify correct greedy strategy for interval scheduling

   Sorting meetings by earliest finish time and picking those that start after last chosen meeting's end maximizes count.

2. Step 2: Explain why earliest start time fails

   Picking by earliest start time may select long meetings first, blocking many others, reducing total count.

3. Final Answer:

   Sort by earliest finish time and pick greedily; earliest start time fails because it may pick long meetings blocking others -> Option D

4. Quick Check:

   Earliest finish time sorting = max meetings [OK]

Hint: Sort by finish time, not start time, for max meetings [OK]

Common Mistakes:

• Sorting by start time only
• Ignoring meeting durations
• Assuming random picks work