Why Greedy Works and When It Fails in DSA Java - 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 value quickly. This project will help you understand how a greedy approach works and when it might fail.

🎯 Goal: You will create a simple Java program that uses a greedy method to select tasks based on their value and time. Then, you will see a case where greedy does not give the best result.

📋 What You'll Learn

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

Add a time limit variable

Implement a greedy selection based on value/time ratio

Show the selected tasks and total value

Demonstrate a case where greedy fails to find the best solution

💡 Why This Matters

🌍 Real World

Greedy algorithms are used in scheduling, resource allocation, and many quick decision-making problems where a fast, good-enough solution is needed.

💼 Career

Understanding when greedy algorithms work or fail helps software engineers choose the right approach for optimization problems in real projects.

1

Create the list of tasks

Create a class called Task with String name, int value, and int time. Then create an ArrayList<Task> called tasks and add these exact tasks: ("A", 10, 2), ("B", 15, 3), ("C", 20, 5).

DSA Java

// Define Task class and create tasks list
// Your code here

Hint

Define the Task class first, then create the tasks list and add the tasks exactly as given.

2

Add the time limit

Add an int variable called timeLimit and set it to 5.

DSA Java

import java.util.ArrayList;

class Task {
    String name;
    int value;
    int time;

    Task(String name, int value, int time) {
        this.name = name;
        this.value = value;
        this.time = time;
    }
}

public class GreedyExample {
    public static void main(String[] args) {
        ArrayList tasks = new ArrayList();
        tasks.add(new Task("A", 10, 2));
        tasks.add(new Task("B", 15, 3));
        tasks.add(new Task("C", 20, 5));
        // Add timeLimit variable below
        // Your code here
    }
}

Hint

Just add int timeLimit = 5; inside the main method.

3

Select tasks greedily by value/time ratio

Sort the tasks list by descending value/time ratio. Then select tasks in this order while the total time does not exceed timeLimit. Store selected tasks in an ArrayList<Task> called selectedTasks. Use variables totalTime and totalValue to track time and value.

DSA Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

class Task {
    String name;
    int value;
    int time;

    Task(String name, int value, int time) {
        this.name = name;
        this.value = value;
        this.time = time;
    }
}

public class GreedyExample {
    public static void main(String[] args) {
        ArrayList tasks = new ArrayList();
        tasks.add(new Task("A", 10, 2));
        tasks.add(new Task("B", 15, 3));
        tasks.add(new Task("C", 20, 5));
        int timeLimit = 5;
        // Sort tasks by value/time ratio descending
        // Select tasks greedily
        // Your code here
    }
}

Hint

Sort tasks by value/time ratio descending using Collections.sort and a Comparator. Then pick tasks while total time is within timeLimit.

4

Print selected tasks and show greedy failure example

Print the names of tasks in selectedTasks separated by commas, and print totalValue. Then add a comment explaining that greedy fails if a task with high value but long time is skipped for smaller tasks with less total value.

DSA Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

class Task {
    String name;
    int value;
    int time;

    Task(String name, int value, int time) {
        this.name = name;
        this.value = value;
        this.time = time;
    }
}

public class GreedyExample {
    public static void main(String[] args) {
        ArrayList tasks = new ArrayList();
        tasks.add(new Task("A", 10, 2));
        tasks.add(new Task("B", 15, 3));
        tasks.add(new Task("C", 20, 5));
        int timeLimit = 5;

        Collections.sort(tasks, new Comparator() {
            public int compare(Task t1, Task t2) {
                double r1 = (double) t1.value / t1.time;
                double r2 = (double) t2.value / t2.time;
                return Double.compare(r2, r1);
            }
        });

        ArrayList selectedTasks = new ArrayList();
        int totalTime = 0;
        int totalValue = 0;

        for (Task t : tasks) {
            if (totalTime + t.time <= timeLimit) {
                selectedTasks.add(t);
                totalTime += t.time;
                totalValue += t.value;
            }
        }

        // Print selected task names separated by commas
        // Print totalValue
        // Add a comment explaining greedy failure
        // Your code here
    }
}

Hint

Print the selected task names separated by commas on one line, then print the total value on the next line. Add a comment about greedy failure.

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