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)