Activity Selection Problem

Photo by Pankaj Patel on Unsplash

It is an optimization technique.

Objective -

Let’s suppose there are N activities along with their start and finish time.

we have to find how many non-conflicting activities we can solve given only single user is there.

Terminologies used

1. Start Time- It is the time when the activity is started.
2. Finish Time- It is the time when the activity is finished.
3. Conflicting activities- Two activities i and j are said to be non-conflicting if Start(i) < Finish(j) or start(j) < Finish(i).

Start(i), Start(j) : Start time

Finish(i), Finish(j) : Finish time

Let us suppose there are two activities A and B.

Activity A has Start time = 2 and Finish time = 4

Activity B has Start time = 3 and Finish time = 4.

Here these activities are known as conflicting activities as the Activity B starts before the completion of Activity A.

4. Non-conflicting Activities-Two activities i and j are said to be non-conflicting if Start(i) ≥ Finish(j) or start(j) ≥ Finish(i).

Start(i), Start(j) : Start time

Finish(i), Finish(j) : Finish time

Example :-

Activity A has Start time = 2 and Finish time = 4

Activity B has Start time = 5 and Finish time = 9.

Here these activities are known as Non-conflicting / Mutually compatible activities as the Activity B starts after the completion of Activity A.

Greedy Method approach to solve this problem:-

Steps followed are :-

1. Sort the given activities in ascending order according to their finished time.
2. Select the first activity from the sorted array and add it to the solution set.
3. Select the next activity from the sorted array.
4. If the start time of currently selected activity is greater than or equal to the previously selected activity then add it to the solution set.
5. Repeat steps 4 and 5 for remaining activities.

Let’s understand these steps by taking an example —

1. Sort the given activities in ascending order according to their finish time.

After sorting the above activity table in ascending order :-

2. Then create a solution array= {}.

3. Select the 1st activity of the sorted array and add it to the solution array.

Solution array= { B }

4. Then after that find the next best activity from the sorted array whose start time is greater than or equal to finish time of B(i.e, 2).

So the next activity to be solved is C. Add C to the solution array.

Solution array = {B, C }

5. Then find the next best activity from the sorted array whose start time is greater than or equal to finish time of C (i.e, 4).

So the next activity to be solved is E. Add E to the solution set.

Solution array = {B, C ,E}

6.Then find the next best activity from the sorted array whose start time is greater than or equal to finish time of E(i.e, 7).

So the next activity to be solved is F. Add F to the solution array.

Solution array = {B, C ,E,F}

So we can solve maximum 4 non-conflicting activities given only a single user is there.

Here is one question you can try :-

Mail the answer to my email Id — littlebeautybisoyi@gmail.com for knowing the correct answer or any queries.