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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <vector>
#include <sstream>

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<activity> get_activities( std::istream& stm )
{
    std::vector<activity> 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 <fstream>
     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<activity> 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<activity> solve( std::vector<activity> 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.
Registered users can post here. Sign in or register to post.