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

Why Greedy Works and When It Fails

📖 Scenario: Imagine you are organizing a small event and need to select tasks to complete within a limited time. You want to pick tasks that give you the most benefit quickly. This project will help you understand how a greedy approach can help make decisions fast, and also when it might not give the best result.

🎯 Goal: You will create a simple program in C++ that uses a greedy method to select tasks based on their benefit-to-time ratio. Then, you will see what happens when this approach fails by comparing it to a different selection.

📋 What You'll Learn

Create a list of tasks with exact names, times, and benefits

Add a time limit variable to select tasks within

Implement a greedy selection based on benefit/time ratio

Print the selected tasks and total benefit

💡 Why This Matters

🌍 Real World

Greedy algorithms are used in scheduling, resource allocation, and decision making where quick, good-enough solutions are needed.

💼 Career

Understanding when greedy works or fails helps in software development, especially in optimization problems and algorithm design.

1

Create the list of tasks

Create a vector of tasks called tasks. Each task is a struct with name (string), time (int), and benefit (int). Add these exact tasks: {"TaskA", 3, 50}, {"TaskB", 1, 20}, {"TaskC", 2, 30}, {"TaskD", 4, 70}.

DSA C++

#include 
#include 
#include 

struct Task {
    std::string name;
    int time;
    int benefit;
};

int main() {
    // Create vector tasks with given tasks
    // Your code here
    return 0;
}

Hint

Define a struct Task with name, time, and benefit. Then create a vector called tasks with the exact tasks listed.

2

Add the time limit

Add an integer variable called time_limit and set it to 5. This is the maximum total time allowed for selecting tasks.

DSA C++

#include 
#include 
#include 

struct Task {
    std::string name;
    int time;
    int benefit;
};

int main() {
    std::vector tasks = {
        {"TaskA", 3, 50},
        {"TaskB", 1, 20},
        {"TaskC", 2, 30},
        {"TaskD", 4, 70}
    };
    // Add int time_limit = 5
    // Your code here
    return 0;
}

Hint

Just add a variable time_limit and set it to 5.

3

Select tasks using greedy approach

Sort the tasks vector in descending order by benefit/time ratio. Then, create a vector called selected to store chosen tasks. Use a for loop with variable task to iterate over tasks. Add task to selected if total time does not exceed time_limit. Keep track of total time with used_time initialized to 0.

DSA C++

#include 
#include 
#include 
#include 

struct Task {
    std::string name;
    int time;
    int benefit;
};

int main() {
    std::vector tasks = {
        {"TaskA", 3, 50},
        {"TaskB", 1, 20},
        {"TaskC", 2, 30},
        {"TaskD", 4, 70}
    };
    int time_limit = 5;
    // Sort tasks by benefit/time descending
    // Create vector selected
    // Use for loop with task to select tasks within time_limit
    // Your code here
    return 0;
}

Hint

Sort tasks by benefit/time ratio descending. Then pick tasks one by one if total time stays within time_limit.

4

Print selected tasks and total benefit

Use a for loop with variable task to print each selected task's name. Then, calculate and print the total benefit of all selected tasks with the exact text format: Total benefit: X where X is the sum of benefits.

DSA C++

#include 
#include 
#include 
#include 

struct Task {
    std::string name;
    int time;
    int benefit;
};

int main() {
    std::vector tasks = {
        {"TaskA", 3, 50},
        {"TaskB", 1, 20},
        {"TaskC", 2, 30},
        {"TaskD", 4, 70}
    };
    int time_limit = 5;

    std::sort(tasks.begin(), tasks.end(), [](const Task& a, const Task& b) {
        double r1 = (double)a.benefit / a.time;
        double r2 = (double)b.benefit / b.time;
        return r1 > r2;
    });

    std::vector selected;
    int used_time = 0;
    for (const Task& task : tasks) {
        if (used_time + task.time <= time_limit) {
            selected.push_back(task);
            used_time += task.time;
        }
    }
    // Print selected task names
    // Calculate and print total benefit with format: Total benefit: X
    // Your code here
    return 0;
}

Hint

Print each selected task's name on its own line. Then print total benefit exactly as Total benefit: X.

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 paths

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 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 and optimal substructure.

3. Final Answer:

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

4. Quick Check:

   Greedy = local best choice [OK]

Hint: Greedy picks best now, not all possibilities [OK]

Common Mistakes:

• Thinking greedy tries all solutions
• Confusing greedy with backtracking
• Assuming sorting alone makes greedy work

2. Which of the following is the correct syntax to select the next item in a greedy algorithm loop in C++?

easy

A. for (auto item : items) { choose item; }

B. for (int i = 0 i < n; i++) { choose item[i]; }

C. while (i <= n) { choose item[i]; i++; }

D. do { choose item[i]; i--; } while (i > 0);

Solution

1. Step 1: Identify correct C++ loop syntax for iteration

   The range-based for loop for (auto item : items) is modern and correct for iterating over a container.

2. Step 2: Check other options for correctness

   for (int i = 0 i < n; i++) { choose item[i]; } is missing semicolons and proper syntax. while (i <= n) { choose item[i]; i++; } uses while but lacks initialization shown. do { choose item[i]; i--; } while (i > 0); decrements i incorrectly.

3. Final Answer:

   for (auto item : items) { choose item; } -> Option A

4. Quick Check:

   Range-based for loop is correct syntax [OK]

Hint: Use range-based for loops for clean iteration [OK]

Common Mistakes:

• Missing semicolons in for loop
• Using wrong loop conditions
• Decrementing index when should increment

3. Consider the following C++ code snippet for selecting intervals greedily by earliest finish time:

struct Interval {
  int start, end;
};

bool compare(Interval a, Interval b) {
  return a.end < b.end;
}

int main() {
  std::vector<Interval> intervals = {{1,4}, {3,5}, {0,6}, {5,7}, {8,9}};
  std::sort(intervals.begin(), intervals.end(), compare);
  int count = 0, last_end = -1;
  for (auto interval : intervals) {
    if (interval.start >= last_end) {
      count++;
      last_end = interval.end;
    }
  }
  std::cout << count << std::endl;
  return 0;
}

What is the output of this program?

medium

A. 5

B. 4

C. 3

D. 2

Solution

1. Step 1: Sort intervals by end time

   Sorted intervals by end: {1,4}, {3,5}, {0,6}, {5,7}, {8,9}

2. Step 2: Select intervals greedily

   Select {1,4} (count=1, last_end=4), skip {3,5} (start 3 < 4), skip {0,6} (start 0 < 4), select {5,7} (start 5 >= 4, count=2, last_end=7), select {8,9} (start 8 >= 7, count=3, last_end=9)

3. Step 3: Count total selected intervals

   Total selected intervals = 3

4. Final Answer:

   3 -> Option C

5. Quick Check:

   Greedy interval selection count = 3 [OK]

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

Common Mistakes:

• Counting overlapping intervals
• Not sorting intervals correctly
• Updating last_end incorrectly

4. The following code attempts to solve the coin change problem using a greedy approach:

int coins[] = {25, 10, 5, 1};
int amount = 30;
int count = 0;
for (int i = 0; i < 4; i++) {
  while (amount >= coins[i]) {
    amount -= coins[i];
    count++;
  }
}
std::cout << count << std::endl;

What is the main issue with this greedy approach?

medium

A. It always gives the minimum number of coins

B. It may fail for some coin sets where greedy is not optimal

C. It causes a syntax error due to missing semicolons

D. It runs infinitely because amount never decreases

Solution

1. Step 1: Understand greedy coin change approach

   The code picks largest coin repeatedly until amount is reduced to zero.

2. Step 2: Identify greedy failure cases

   Greedy works for US coins but fails for some coin sets where smaller coins combined give fewer coins than greedy picks.

3. Final Answer:

   It may fail for some coin sets where greedy is not optimal -> Option B

4. Quick Check:

   Greedy coin change can fail [OK]

Hint: Greedy coin change fails on non-canonical coin sets [OK]

Common Mistakes:

• Assuming greedy always gives minimum coins
• Confusing syntax errors with logic errors
• Ignoring infinite loop possibility

5. You want to select activities to attend from a list with start and end times. The greedy algorithm picks the earliest finishing activity first. However, if activities have the same end time, it picks the one with the earliest start time. Why might this tie-break rule cause the greedy algorithm to fail in some cases?

hard

A. Because tie-break rules do not affect greedy correctness

B. Because earliest start time always leads to the best solution

C. Because sorting by end time is not needed in greedy algorithms

D. Because picking earliest start time among ties may block more future activities

Solution

1. Step 1: Understand tie-breaking in activity selection

   Greedy sorts by earliest finish time. Ties in end time use earliest start as tie-breaker.

2. Step 2: Analyze effect on greedy selection

   Picking the earliest start time among tied end times may block more future activities, reducing the total number of activities selected.

3. Step 3: Confirm impact on optimality

   This tie-break rule can cause the greedy algorithm to fail to find the maximum set of non-overlapping activities.

4. Final Answer:

   Because picking earliest start time among ties may block more future activities -> Option D

5. Quick Check:

   Tie-break can affect future selections [OK]

Hint: Tie-breaks can affect greedy correctness when ends tie [OK]

Common Mistakes:

• Thinking tie-breaks do not affect optimality
• Assuming all tie-breaks are harmless
• Ignoring impact of start times on future choices