Log In Sign Up
Day 41

Day 41: Activity Selection Problem

41/60 Days

Activity Selection Problem #

Welcome to Day 41 of our 60 Days of Coding Algorithm Challenge! Today, we’ll dive deep into the Activity Selection Problem, a classic example of how greedy algorithms can be used to solve optimization problems efficiently.

What is the Activity Selection Problem? #

The Activity Selection Problem involves selecting the maximum number of non-overlapping activities that can be performed by a single person or machine, given a set of activities with their start and finish times.

Problem Statement #

Given n activities with their start and finish times, select the maximum number of activities that can be performed by a single person, assuming that a person can only work on a single activity at a time.

Greedy Approach #

The greedy approach to solve this problem is to always pick the next activity with the earliest finish time. This approach works because choosing the activity with the earliest finish time leaves more room for other activities.

Implementation #

Let’s implement the Activity Selection Problem using Python:

 1def activity_selection(start, finish):
 2    n = len(start)
 3    
 4    # Sort activities by …