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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Greedy Coin Change Algorithm

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

DSA Java

import java.util.*;
public class GreedyCoinChange {
    public static void main(String[] args) {
        int[] coins = {25, 10, 5, 1};
        int amount = 30;
        List<Integer> result = new ArrayList<>();
        for (int coin : coins) {
            while (amount >= coin) {
                amount -= coin;
                result.add(coin);
            }
        }
        System.out.println(result);
    }
}

A [25, 1, 1, 1, 1, 1]

B [10, 10, 10]

C [25, 5]

D [5, 5, 5, 5, 5, 5]

💡 Hint

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

The greedy algorithm picks the largest coin less than or equal to the remaining amount. For 30, it picks 25 once, then 5 once, totaling 30. So the output list is [25, 5].

🧠 Conceptual

intermediate

When Does Greedy Fail in Coin Change?

Given coin denominations of 1, 3, and 4, what is the minimum number of coins needed to make change for 6 using a greedy approach that always picks the largest coin possible first?

A 2 coins

B 1 coin

C 4 coins

D 3 coins

💡 Hint

Try to pick the largest coin first and see how many coins you end up with.

Greedy picks 4 first, then 1, then 1, totaling 3 coins. But the optimal solution is 2 coins (3 + 3). So greedy fails here.

🔧 Debug

advanced

Identify the Bug in Greedy Interval Scheduling

Consider the following Java code that tries to select the maximum number of non-overlapping intervals using a greedy approach. What is the bug that causes it to fail for some inputs?

DSA Java

import java.util.*;
class Interval {
    int start, end;
    Interval(int s, int e) { start = s; end = e; }
}
public class IntervalScheduling {
    public static void main(String[] args) {
        Interval[] intervals = {
            new Interval(1, 4),
            new Interval(3, 5),
            new Interval(0, 6),
            new Interval(5, 7),
            new Interval(8, 9),
            new Interval(5, 9)
        };
        Arrays.sort(intervals, (a, b) -> a.start - b.start);
        List<Interval> selected = new ArrayList<>();
        int lastEnd = -1;
        for (Interval interval : intervals) {
            if (interval.start >= lastEnd) {
                selected.add(interval);
                lastEnd = interval.end;
            }
        }
        System.out.println(selected.size());
    }
}

A Sorting intervals by start time instead of end time causes suboptimal selection.

B Using 'lastEnd' initialized to -1 causes an off-by-one error.

C The condition 'interval.start >= lastEnd' should be 'interval.end > lastEnd'.

D The intervals array is not sorted at all, causing random output.

💡 Hint

Think about which sorting order guarantees the greedy choice is optimal.

The greedy algorithm for interval scheduling must sort intervals by their end times to pick the earliest finishing intervals first. Sorting by start time can lead to suboptimal results.

🚀 Application

advanced

Greedy Algorithm for Activity Selection Output

Given activities with start and end times: (1,2), (3,4), (0,6), (5,7), (8,9), (5,9), what is the output list of selected activities (by their start times) using the greedy algorithm that selects activities by earliest finish time?

DSA Java

import java.util.*;
class Activity {
    int start, end;
    Activity(int s, int e) { start = s; end = e; }
    public String toString() { return "(" + start + "," + end + ")"; }
}
public class ActivitySelection {
    public static void main(String[] args) {
        Activity[] activities = {
            new Activity(1, 2),
            new Activity(3, 4),
            new Activity(0, 6),
            new Activity(5, 7),
            new Activity(8, 9),
            new Activity(5, 9)
        };
        Arrays.sort(activities, (a, b) -> a.end - b.end);
        List<Activity> selected = new ArrayList<>();
        int lastEnd = -1;
        for (Activity act : activities) {
            if (act.start >= lastEnd) {
                selected.add(act);
                lastEnd = act.end;
            }
        }
        System.out.println(selected);
    }
}

A [(1,2), (5,7), (8,9)]

B [(1,2), (3,4), (5,7), (8,9)]

C [(0,6), (8,9)]

D [(3,4), (5,9)]

💡 Hint

Select activities that finish earliest and do not overlap with previously selected ones.

Sorting by end time and selecting compatible activities yields (1,2), (3,4), (5,7), (8,9).

🧠 Conceptual

expert

Why Greedy Algorithm Fails for 0/1 Knapsack Problem

Why does the greedy algorithm that picks items with the highest value-to-weight ratio first fail to always find the optimal solution for the 0/1 Knapsack problem?

A Because it only works when items can be broken into fractions, not when items are indivisible.

B Because it sorts items by weight instead of value, leading to wrong choices.

C Because it always picks the heaviest items first, ignoring their value.

D Because it does not consider the total weight limit and may pick items that prevent better combinations.

💡 Hint

Think about the difference between fractional and 0/1 knapsack problems.

Greedy works for fractional knapsack where items can be split, but fails for 0/1 knapsack because items are indivisible and picking the best ratio first may block better overall combinations.

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