A greedy algorithm is an approach to solving a problem by making the locally optimal choice at each
stage with the hope of finding a global optimum. In many cases, a greedy strategy does not produce
the optimal solution, but for some problems, it can.
The core idea of a greedy algorithm is to build a solution incrementally, one piece at a time. At each
step, it chooses the best available option without considering future consequences. This makes
greedy algorithms simple and fast, but not always correct.
A classic example where a greedy approach works is the activity selection problem.
Activity Selection Problem
Problem: Given a set of activities with their start and finish times, find the maximum number of non-
overlapping activities that can be performed by a single person.
Greedy Strategy:
1. Sort: Sort the activities by their finish times in non-decreasing order.
2. Select: Select the first activity from the sorted list.
3. Iterate: Iterate through the remaining activities. If an activity's start time is greater than or
equal to the finish time of the last selected activity, select it.
4. Repeat: Continue this process until all activities have been considered.
This strategy works because by choosing the activity that finishes earliest, we leave the maximum
amount of time available for subsequent activities.
Python Code for Activity Selection
Here is a Python implementation of the greedy algorithm for the activity selection problem:
Python
def greedy_activity_selector(activities):
"""
Selects the maximum number of non-overlapping activities.
Args:
activities: A list of tuples, where each tuple contains (start_time, finish_time).
Returns:
A list of selected activities.
"""
if not activities:
return []
# Sort activities by their finish times
activities.sort(key=lambda x: x[1])
# The first activity in the sorted list is always selected
selected_activities = [activities[0]]
# The finish time of the last selected activity
last_finish_time = activities[0][1]
# Iterate through the rest of the activities
for i in range(1, len(activities)):
current_activity_start_time = activities[i][0]
# If the current activity's start time is after or equal to the last
# selected activity's finish time, select it
if current_activity_start_time >= last_finish_time:
selected_activities.append(activities[i])
last_finish_time = activities[i][1]
return selected_activities
# Example usage
activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
selected = greedy_activity_selector(activities)
print("Original activities (start, finish):")
print(activities)
print("\nMaximum number of non-overlapping activities:")
print(selected)
Explanation of the Code:
1. Function Definition: The greedy_activity_selector function takes a list of activities as input,
where each activity is a tuple of (start_time, finish_time).
2. Sorting: activities.sort(key=lambda x: x[1]) sorts the list of activities based on their finish
times. This is the crucial greedy step. The lambda function is used to specify that the sorting
key is the second element of each tuple (the finish time).
3. Initialization: The selected_activities list is initialized with the first activity from the sorted
list, as it will always be part of the solution. last_finish_time is set to the finish time of this
first activity.
4. Iteration and Selection: The code then iterates through the remaining activities. For each
activity, it checks if its start time is greater than or equal to last_finish_time. This condition
ensures that the new activity does not overlap with the previously selected one.
5. Updating: If the condition is met, the activity is added to the selected_activities list, and
last_finish_time is updated to the finish time of this newly selected activity.
6. Return Value: The function returns the list of activities that were selected.
The output for the given example will be [(1, 4), (5, 7), (8, 11), (12, 16)], which is the correct set of
non-overlapping activities.
