Question

Qu 1:
(a) Suppose that instead of always selecting the first activity to finish, we select the last activity to start that is compatible with all previously selected activities. In the case, the activities are assumed to be sorted in increasing order of start time.
Modify the Greedy_Activity_Selector algorithm to work with this approach to find a subset of maximum number of mutually compatible activities.

(b) Use the following list of activities to show how your algorithm in (a) above will work to find a
maximum set of mutually compatible activities.

Activity	start time	Finish time
1	0	6
2	1	4
3	2	12
4	3	5
5	3	7
6	5	8
7	5	9
8	6	10
9	8	12
10	9	11
11	12	14

Note: Show your result graphically, highlighting the selected activities with a
different color.

Answer 1

Solution :-

C++ Code :-

#include<bits/stdc++.h>
using namespace std;

// structure to hold activity data
struct Activity
{
int startTime;
int finishTime;
};
int main()
{
int numActivity;
cout<<"Enter number of activities :- \n"<<endl;
cin>>numActivity;

Activity activities[numActivity];

cout<<"Enter start time and finish time for activities :-"<<endl;

for(int i=0;i<numActivity;i++)
{
cout<<"Enter for activity "<<i+1<<" :- ";

cin>>activities[i].startTime>>activities[i].finishTime;
}

// Apply the algorithm for result

vector<Activity> result; // vector to hold the activities included in resultant set

int last = numActivity - 1; // index of last included activity

result.push_back(activities[numActivity - 1]);

for(int i=numActivity-2;i>=0;i--)
{
// include the activity only if it is compatible with already included
if(activities[i].finishTime <= activities[last].startTime)
{
result.push_back(activities[i]);
last = i;
}
}

cout<<"Maximum number of activities that you can carry out is "<<result.size()<<endl;

cout<<"Activities included :- ";

for(int i=result.size()-1;i>=0;i--)
{
cout<<"{"<<result[i].startTime<<", "<<result[i].finishTime<<"} ";
}
cout<<endl;
}

Sample input/output :-

Enter number of activities :-

11
Enter start time and finish time for activities :-
Enter for activity 1 :- 0 6
Enter for activity 2 :- 1 4
Enter for activity 3 :- 2 12
Enter for activity 4 :- 3 5
Enter for activity 5 :- 3 7
Enter for activity 6 :- 5 8
Enter for activity 7 :- 5 9
Enter for activity 8 :- 6 10
Enter for activity 9 :- 8 12
Enter for activity 10 :- 9 11
Enter for activity 11 :- 12 14
Maximum number of activities that you can carry out is 4
Activities included :- {3, 5} {5, 9} {9, 11} {12, 14}