Greedy Method Example

Example-1

Activity Selection Problem

Problem:

You are given n activities with start and finish times. Your goal is to select the maximum number of activities that don't overlap.

Input:

• List of activities with their start and finish times.
  • Activity 1: Start = 1, End = 4
  • Activity 2: Start = 3, End = 5
  • Activity 3: Start = 0, End = 6
  • Activity 4: Start = 5, End = 7
  • Activity 5: Start = 8, End = 9
  • Activity 6: Start = 5, End = 9

Greedy Strategy:

• Greedy choice: Always pick the activity that finishes the earliest (locally optimal choice).
• The reasoning is that if an activity finishes earlier, more time is left for subsequent activities.

Steps:

1. Sort the activities by their finish times.

   • Sorted activities: (Activity 1: 1,4), (Activity 2: 3,5), (Activity 3: 0,6), (Activity 4: 5,7), (Activity 5: 8,9), (Activity 6: 5,9),

2. Pick the first activity in the sorted list (Activity 1).

3. Now, check the next activity. If it starts after the current activity ends, select it.

   • Select Activity 4 (because it starts at 5 after Activity 1 ends at 4).

4. Continue this process:

   • Select Activity 5 (because it starts at 8 after Activity 4 ends at 7).

So, the maximum number of activities that can be selected is 3: (Activity 1, Activity 4, Activity 5).

Example-2

Problem:

• You are given an array of positive integers where each integer represents the completion time for a task.
• You also have a fixed amount of time T available.
• The goal is to find the maximum number of tasks you can complete within the given time T.

Greedy Approach:

The greedy strategy here is to:

1. Sort the tasks by their completion times in ascending order.
2. Start completing the shortest tasks first, so that you maximize the number of tasks before the available time runs out.

Steps:

1. Sort the array of task completion times.
2. Iterate through the sorted list, adding tasks one by one as long as the total time does not exceed the available time T.
3. Stop when adding the next task would exceed the available time.

Example:

Let’s take an example to understand the approach.

Input:

• Task completion times: [4, 2, 8, 3, 5]
• Available time T = 10

Greedy Method:

1. Sort the tasks: [2, 3, 4, 5, 8]

2. Iterate through the tasks:

   • Task 1 (time 2): Total time = 2, tasks completed = 1.
   • Task 2 (time 3): Total time = 2 + 3 = 5, tasks completed = 2.
   • Task 3 (time 4): Total time = 5 + 4 = 9, tasks completed = 3.
   • Task 4 (time 5): If you add this task, the total time would be 9 + 5 = 14, which exceeds the available time T = 10. So, stop here.

Result:

• The maximum number of tasks that can be completed is 3.

Python code to Implement Task completion Problem

def max_tasks(tasks, T):

    # Sort tasks by their completion time

    tasks.sort()

    

    total_time = 0

    task_count = 0

    

    # Iterate through sorted tasks

    for time in tasks:

        if total_time + time <= T:

            total_time += time

            task_count += 1

        else:

            break

    

    return task_count

# Example usage

tasks = [4, 2, 8, 3, 5]

T = 10

result = max_tasks(tasks, T)

print("Maximum number of tasks that can be completed:", result)

A vending machine needs to return change to a customer using the least number of coins. The machine has an infinite supply of coins of denominations. Implement the greedy algorithm to determine the combination of coins that minimizes the total number of coins used to make a given amount of change. ( university question)

Greedy Algorithm for Making Change

The greedy approach selects the largest denomination coin that does not exceed the remaining amount, subtracts it, and repeats until the amount becomes 0.

Why Greedy Works Here

For many common currency systems, choosing the largest possible coin at each step leads to the least number of coins.

---

Greedy Strategy

1. Sort coin denominations in descending order

2. For each coin:

   • Take as many of that coin as possible

   • Subtract from the amount

3. Repeat until amount becomes 0

---

Python Implementation

def greedy_change(amount, coins):
    coins.sort(reverse=True)  # Step 1: Use largest first
    result = {}               # To store the count of each coin

    for coin in coins:
        if amount >= coin:
            count = amount // coin      # Max number of this coin
            result[coin] = count
            amount = amount % coin      # Remaining amount

    return result

Example usage:

coins = [1, 5, 10, 25]   # Denominations
amount = 67

change = greedy_change(amount, coins)
print(change)

Output:

{25: 2, 10: 1, 5: 1, 1: 2}

➡️ Meaning the machine should return:
2×25 + 1×10 + 1×5 + 2×1 = 67
Total coins = 6 coins, which is minimal.

---

Pseudocode Version 

Algorithm GreedyChange(amount, coins):
    sort coins in descending order
    for each coin in coins:
        if amount >= coin:
            count ← amount // coin
            print coin, "used", count, "times"
            amount ← amount % coin
    end for
end Algorithm

---

Example Walkthrough (Amount = 67, Coins = 25,10,5,1)

1. Take 2 coins of 25 → remaining 17

2. Take 1 coin of 10 → remaining 7

3. Take 1 coin of 5 → remaining 2

4. Take 2 coins of 1 → remaining 0

Total = 6 coins.