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).