### Activity Selection Promblem

I have to take a text file and using a greedy algorithm determine which activities and how many activities I can do in a given set. Here is an example of the text file:

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

So the first set would have eleven activities with the the first one in that set (1 1 4) would be activity 1 starting time of 1 and ending time of 4. I am having trouble with getting started pulling the data into the text file. Any suggestions would be appreciated.
Last edited on
Something like this:

 ``12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576`` ``````#include #include #include struct activity // a struct to hold information about one activity { int number ; int start_time ; int end_time ; }; // https://cal-linux.com/tutorials/vectors.html std::vector get_activities( std::istream& stm ) { std::vector result ; // read the count of activities in this set std::size_t cnt ; if( stm >> cnt ) // if count was read in successfully { // read in up to a max of cnt activities; add each activity to the result activity a ; while( result.size() < cnt && stm >> a.number >> a.start_time >> a.end_time ) result.push_back(a) ; } return result ; } int main() { // simulate input from a test file using a string stream. in the actual program, // replace this with: std::ifstream file( "input_file_name.txt" ) ; // #include std::istringstream file( R"( 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 )" ) ; std::vector activities = get_activities(file) ; // get the first data set int data_set = 0 ; while( !activities.empty() ) // for each data set that was read in successfully { // print out the contents of the data set std::cout << "\n------- data set #" << ++data_set << " (contains " << activities.size() << " activities) -------\n" ; for( const activity& a : activities ) { std::cout << "activity #" << a.number << " start: " << a.start_time << " end: " << a.end_time << '\n' ; } // TO DO: determine how many activities in this set can be performed // ideally, call a function to do that // eg. std::vector solve( std::vector activities ) ; // print the results activities = get_activities(file) ; // get the next data set } }``````

http://coliru.stacked-crooked.com/a/433699fb3511409d
Last edited on
Thanks this was a big help. I don't know why but my brain just deiced to stop working this morning.
Topic archived. No new replies allowed.