Why Greedy Works and When It Fails in DSA Java - Quick Recap

Recall & Review

beginner

What is the main idea behind the greedy algorithm approach?

Greedy algorithms make the best choice at each step, hoping to find the overall best solution by building it piece by piece.

intermediate

What does it mean for a problem to have the 'greedy choice property'?

It means that a locally optimal choice at each step leads to a globally optimal solution.

intermediate

Why does the greedy algorithm fail in some problems?

Because some problems do not have the greedy choice property or optimal substructure, so local best choices do not lead to the best overall solution.

beginner

Give an example of a problem where greedy algorithms work well.

The Activity Selection problem, where choosing the earliest finishing activity first leads to the maximum number of activities selected.

intermediate

Give an example of a problem where greedy algorithms fail to find the best solution.

The Coin Change problem with arbitrary coin denominations, where greedy choice may not give the minimum number of coins.

What property must a problem have for a greedy algorithm to guarantee an optimal solution?

A Backtracking

B Randomness

C Brute force

D Greedy choice property

The greedy choice property ensures that local optimal choices lead to a global optimum.

Which of these problems is a classic example where greedy algorithms work perfectly?

A Activity Selection

B Traveling Salesman

C Knapsack 0/1

D Coin Change with arbitrary coins

Activity Selection problem has the greedy choice property and optimal substructure.

Why might a greedy algorithm fail on the Coin Change problem with coins {1, 3, 4} to make 6?

A Because greedy picks largest coin first and may not minimize total coins

B Because greedy always picks smallest coin first

C Because greedy uses recursion

D Because greedy sorts coins incorrectly

Greedy picks 4 then 1+1, total 3 coins, but optimal is 3+3 = 2 coins.

What is 'optimal substructure' in the context of greedy algorithms?

A Solution is always unique

B Solution requires checking all possibilities

C Optimal solution can be built from optimal solutions of subproblems

D Solution depends on random choices

Optimal substructure means smaller parts of the problem can be solved optimally to build the full solution.

Which of these is NOT a reason greedy algorithms might fail?

A Lack of optimal substructure

B Problem size too large

C Lack of greedy choice property

D Local choices do not lead to global optimum

Problem size affects performance but not correctness of greedy algorithms.

Explain why greedy algorithms work for some problems but fail for others.

Think about how making the best choice at each step affects the overall solution.

Describe a real-life situation where a greedy approach works well and one where it might fail.

Consider picking tasks or spending money with coins.

Practice

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

easy

A. Because it uses recursion to explore all paths

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 sorts the input data before processing

Solution

1. Step 1: Understand greedy choice property

   A greedy algorithm chooses 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.

3. Final Answer:

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

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 now, not all possibilities [OK]

Common Mistakes:

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

2. Which of the following is the correct syntax to start a greedy algorithm loop in Java to process an array arr of length n?

easy

A. foreach (int i : arr)

B. for i in range(0, n):

C. while (i <= n) { i++; }

D. for (int i = 0; i < n; i++)

Solution

1. Step 1: Identify Java loop syntax

   Java uses for loops with initialization, condition, and increment: for (int i = 0; i < n; i++)

2. Step 2: Check options for Java correctness

   for (int i = 0; i < n; i++) matches Java syntax; B is Python, C is incomplete and incorrect, D is incorrect syntax for array iteration.

3. Final Answer:

   for (int i = 0; i < n; i++) -> Option D

4. Quick Check:

   Java for loop syntax = for (int i = 0; i < n; i++) [OK]

Hint: Java for loops use int i=0; i

Common Mistakes:

• Using Python syntax in Java
• Incorrect loop conditions
• Misusing foreach syntax

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

int[][] intervals = {{1,3},{2,5},{4,7}};
Arrays.sort(intervals, (a,b) -> a[1] - b[1]);
int count = 0, end = 0;
for (int[] interval : intervals) {
  if (interval[0] >= end) {
    count++;
    end = interval[1];
  }
}
System.out.println(count);

What is the output?

medium

A. 3

B. 2

C. 1

D. 0

Solution

1. Step 1: Sort intervals by finish time

   Sorted intervals by end time: {1,3}, {2,5}, {4,7}

2. Step 2: Select intervals greedily

   Select {1,3} first (count=1, end=3). Next {2,5} starts at 2 < 3, skip. Next {4,7} starts at 4 >= 3, select (count=2).

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Greedy interval selection = 2 [OK]

Hint: Pick intervals by earliest finish time [OK]

Common Mistakes:

• Not sorting intervals
• Selecting overlapping intervals
• Counting all intervals without check

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

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++;
  }
}
System.out.println(count);

What is the output and what is the problem with this approach?

medium

A. 3; Greedy fails because it doesn't find minimum coins

B. 3; Greedy always finds minimum coins

C. 6; Code has syntax error

D. 0; Code does not run

Solution

1. Step 1: Trace greedy coin selection

   Start with coin 4: amount=6>=4, subtract 4 (amount=2), count=1. Next coin 3: amount=2<3 skip. Next coin 1: amount=2>=1 subtract twice, count=3 total coins.

2. Step 2: Check minimum coins possible

   Minimum coins for 6 are 2 (3+3), but greedy picks 3 coins (4+1+1). Greedy fails here.

3. Final Answer:

   3; Greedy fails because it doesn't find minimum coins -> Option A

4. Quick Check:

   Greedy coin change fails = 3; Greedy fails because it doesn't find minimum coins [OK]

Hint: Greedy may fail if coin set is non-canonical [OK]

Common Mistakes:

• Assuming greedy always finds minimum coins
• Ignoring coin order importance
• Confusing output count with amount

5. You want to schedule the maximum number of non-overlapping meetings in one room. Meetings are given as int[][] meetings = {{0, 30}, {5, 10}, {15, 20}, {25, 35}}. Which greedy strategy will always give the optimal solution and why?

hard

A. Select meetings by earliest finish time because it leaves room for more meetings

B. Select meetings by shortest duration because shorter meetings fit more

C. Select meetings by latest start time because it prioritizes recent meetings

D. Select meetings by earliest start time because it schedules more meetings

Solution

1. Step 1: Understand meeting scheduling problem

   Goal is to maximize non-overlapping meetings in one room.

2. Step 2: Analyze greedy strategies

   Choosing earliest finish time frees room earliest, allowing more meetings after.

3. Step 3: Check other strategies

   Earliest start or shortest duration can cause overlaps or miss optimal sets.

4. Final Answer:

   Select meetings by earliest finish time because it leaves room for more meetings -> Option A

5. Quick Check:

   Earliest finish time = optimal scheduling [OK]

Hint: Pick meetings finishing earliest to fit more [OK]

Common Mistakes:

• Choosing earliest start time
• Picking shortest duration meetings
• Ignoring finish times