Activity Selection Last-to-Start Implementation Submit a copy of all your files

Question

Activity Selection Last-to-Start Implementation
Submit a copy of all your files including the txt files and a README file that explains how to compile and run your code in a ZIP file to TEACH. We will only test execution with an input file named act.txt.

Use C++ to implement the activity selection last-to-start algorithm described in problem 4. Include a verbal description of your algorithm, pseudocode and analysis of the theoretical running time. You do not need to collected experimental running times.

The program should read 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

Note: 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

README.txt

Commands to run the program :

g++ ActivitySelectionProblem.cpp

./a.out

Algo :

Store N activities in ActivityList Vector. Sort the End times of N activities. Print least one. Start from second least and compare previous end time and current start time, if prevEnd <= currentStart, print current activity

Complexity :

O(n*logn)

ActivitySelectionProblem.cpp

#include <iostream>

#include <algorithm>

#include <fstream>

#include <vector>

using namespace std;

struct myActivity{

int index;

int start_time;

int end_time;

// you can use this as alternative to compare

// Remember this!!

bool operator<(const myActivity &rhs) const { return end_time < rhs.end_time; }

};

vector<myActivity> ActivityList;

vector<int> OutputList;

/*

Compare function is defined inorder to use

in-built c++ sort defined in #include <algorithm>

operator overloading approach

*/

bool compare( myActivity activity1,

myActivity activity2)

{

if (activity1.end_time < activity2.end_time) return true;

return false;

}

// main algo

// Greedy approach

// Select the activity with least possible end_time at each step.

void ActivitySelection(int N)

{

// first activity always gets selected

int i = 0;

int OutputSize = 0;

OutputSize++;

OutputList.resize(OutputSize);

OutputList[OutputSize-1] = ActivityList[0].index;

// Consider rest of the activities

for (int j = 1; j < N; j++)

{

// If this activity has start time greater than or

// equal to the finish time of previously selected

// activity, then select it

if (ActivityList[j].start_time >= ActivityList[i].end_time)

{

// cout << "here" ;

// cout << j << " " << ActivityList[j].start_time << " " << ActivityList[i].end_time << endl;

// cout << "(" << arr[j].start << ", "

// << arr[j].finish << "), ";

OutputSize++;

OutputList.resize(OutputSize);

OutputList[OutputSize-1] = ActivityList[j].index;

i = j;

}

}

}

void PrintOutput(int set)

{

int OutputSize = OutputList.size();

cout << "Set " << set << endl;

cout << "Number of activities selected = " << OutputSize << endl;

cout << "Activities:";

for (int i = 0; i < OutputSize; ++i)

{

cout << " " << OutputList[i];

}

cout << endl;

}

int main()

{

string filename;

// cout << "Please provide filename: ";

// cin >> filename;

filename = "act.txt";

ifstream myFile(filename);

if (myFile.is_open())

{

int N = 0; // Number of acitivities

int set = 0;

// for each set of activities

while(!myFile.eof())

{

ActivityList.resize(0);

myFile >> N;

for (int i = 0; i < N; ++i)

{

ActivityList.resize(i+1);

myFile >> ActivityList[i].index;

myFile >> ActivityList[i].start_time;

myFile >> ActivityList[i].end_time;

// cout << ActivityList[i].index << " " << ActivityList[i].start_time << " " << ActivityList[i].end_time << endl;

}

sort(ActivityList.begin(), ActivityList.end(), compare);

// cout << ActivityList.size() << endl;

// end of reading from file

// Sorting activities based on End time

ActivitySelection(N);

set++;

PrintOutput(set);

}

myFile.close();

}

else

{

cout << "Unable to open file";

}

return 0;

}

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

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.