In C++ and using a greedy algorithm do the following, create a program that read
ID: 3917005 • Letter: I
Question
In C++ and using a greedy algorithm do the following, create a program that reads input from a file named “act.txt”. The file contains lists of activity sets with number of activities in the set in the first line followed by lines containing the activity number, start time & finish time.
Example act.txt:
11
1 1 4
2 3 5
3 0 6
4 5 7
5 3 9
6 5 9
7 6 10
8 8 11
9 8 12
10 2 14
11 12 16
3
3 6 8
1 7 9
2 1 2
In the above example the first activity set contains 11 activities with activity 1 starting at time 1 and finishing at time 4, activity 2 starting at time 3 and finishing at time 5, etc.. The second activity set contains 3 activities with activity 3 starting at time 6 and finishing at time 8 etc. The activities in the file are not in any sorted order. Your results including the number of activities selected and their order should be outputted to the terminal. For the above example the results are:
Set 1 Number of activities selected = 4
Activities: 2 4 9 11
Set 2 Number of activities selected = 2
Activities: 2 1
There is an alternative optimal solution for Set 1. Since activities 8 and 9 have the same start time of 8, a2 a4 a8 a11 would be an alternative solution. Your program only needs to find one of the optimal solutions. For either solution the activities differ from the solution presented in the text which uses the earliest-finish time criteria.
Explanation / Answer
#include <bits/stdc++.h>
using namespace std;
struct Act //Structure to hold the activity number, its start time and its finish time.
{
int s, f, no;
};
bool activityCompare(Act s1, Act s2) //Sort activities according to their finish times
{
return (s1.f < s2.f);
}
void findMaxAct(Act arr[], int n)
{
int results[100],len=0; //result array will store the optimal set activities number and len will contain the number of activities in the optimal set
sort(arr, arr+n, activityCompare); //Sort the activities according to the finish time.
int i = 0;
results[len]=arr[i].no; //First activity after sorting will always considered to be in the optimal set
++len;
for (int j = 1; j < n; j++)
{
if (arr[j].s >= arr[i].f) //We pick the next activity which has its start time more than or equal to the the current activity finish time.
{
results[len]=arr[j].no;
len++; i = j;
}
}
cout<<"Number of activities selected = "<<len<<endl<<"Activities: ";
for(i=0;i<len;i++) cout<<results[i]<<" ";
cout<<endl;
}
int main()
{
int n;
ifstream inFile; //Input stream object
inFile.open("input.txt"); //Input file name is 'input.txt'
if(!inFile) //If the input file is not there in the same directory, print appropriate message
{
cout<<"Unable to open file";
exit(1);
}
Act arr[100]; //Array of structures for storing activities number, start time and finish time
while(inFile>>n)
{
for(int i=0;i<n;i++)
{
inFile>>arr[i].no;
inFile>>arr[i].s; inFile>>arr[i].f;
}
findMaxAct(arr, n); //Here the optimal solution considered is to pick activities as much as we can.
}
inFile.close();
return 0;
}