Activity Selection Problem

                              By Utkarsh Gore (S.E CSE-AI Roll No : 48 )

 

What is Activity Selection Problem ( ASP ) ?

The Activity Selection Problem is an optimization problem you encounter in scheduling. Expand more Imagine you have a bunch of tasks you want to get done, but you can only work on one thing at a time. Each task has a start and end time . Expand more The Activity Selection Problem asks you to pick the maximum number of tasks you can complete without any overlap.

Example :

• You're given a set of activities, each with a start time (si) and a finish time (fi).
• You can only do one activity at a time.
• Two activities i and j are considered compatible if they don't overlap (si ≥ fi or sj ≥ fi).
•  The problem is to find the maximum set of compatible activities (i.e., the ones you can actually do).

This problem is a classic example of using a Greedy Algorithm for optimization . The Greedy Algorithm works by making the seemingly best choice at every step, hoping it leads to the overall best outcome . In the Activity Selection Problem, the greedy approach involves sorting the activities by their finish time and then picking the activities that don't conflict with the ones you've already chosen.

 

Approaches to Activity Selection Problem ( ASP )

There are mainly Two approaches :-

1.    Greedy Algorithm .
2.  Dynamic Programming

·       Count the maximum number of non-conflicting activities .

·       Print the maximum number of non-conflicting activities .

1.Greedy Algorithm

This method uses the greedy approach and as the name suggests greedy means that at every step we have to make a choice that looks best at the moment and can provide us with an optimal solution for that problem .

Since we have to maximize the number of performed activities, so we will be choosing the activity that will finish first as that will leave us with the maximum time to process the remaining activities. This greedy intuition enables us to make choices and provide us with an optimal solution and also helps us to get started with the solution. Therefore, our first task is to sort the activities based on their finish time.

If we try to solve this problem by sorting the activities based on start time then there might be a case where the activity with the least start time takes maximum duration to complete thus preventing us from maximizing the number of activities.

Algorithm

• Sort all activities based on their finish time.
• Choosing the first activity from the sorted list.
• Select the next activity from the sorted list only if its start time is greater than or equal to the finish time of the previously selected activity.
• Repeat Step 3 for all the remaining activities in the sorted list.

·        

Question

we have 6 activities with corresponding start and end time, the objective is to compute an execution schedule having maximum number of non-conflicting activities

Start Time ( S )	Finish Time ( F )	Activity Name
5	9	a1
1	2	a2
3	4	a3
0	6	a4
5	7	a5
8	9	a6

 

Answer

Step 1: Sort the given activities in ascending order according to their finishing time.

The table after we have sorted it :

Start Time ( S )	Finish Time ( F )	Activity Name
1	2	a2
3	4	a3
0	6	a4
5	7	a5
5	9	a1
8	9	a6

 

Step 2: Select the first activity from sorted array act[] and add it to the sol[] array, thus sol = {a2}.

Step 3: Repeat the steps 4 and 5 for the remaining activities in act[].

Step 4: If the start time of the currently selected activity is greater than or equal to the finish time of the previously selected activity, then add it to sol[].

Step 5: Select the next activity in act[]

For the data given in the above table,

Select activity a3. Since the start time of a3 is greater than the finish time of a2 (i.e. s(a3) > f(a2)), we add a3 to the solution set. Thus sol = {a2, a3}.

Select a4. Since s(a4) < f(a3), it is not added to the solution set.

Select a5. Since s(a5) > f(a3), a5 gets added to solution set. Thus sol = {a2, a3, a5}

Select a1. Since s(a1) < f(a5), a1 is not added to the solution set.

Select a6. a6 is added to the solution set since s(a6) > f(a5). Thus sol = {a2, a3, a5, a6}.

Step 6: At last, print the array sol[]

Hence, the execution schedule of maximum number of non-conflicting activities will be:

(1,2)

(3,4)

(5,7)

(8,9)