Let S a1 a2 a3 a12 be a set with n 12 activities The start

Let S= (a_1, a_2, a_3...., a_12} be a set with n = 12 activities. The start time and the finish time of each activity is shown in the table below. Run the GREEDY-ACTIVITY-SELECTOR function learned in class. What is the subset of activities returned? Write the activities in the correct order in which they are selected by the algorithm.

Solution

Following activities are selected
Activity with start time: 1 and end time: 5
Activity with start time: 6 and end time: 8
Activity with start time: 8 and end time: 10
Activity with start time: 11 and end time: 12
Activity with start time: 12 and end time: 15
Activity with start time: 16 and end time: 18

Following is the C++ code used to generate the output:

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;

void greedyActivitySelector( int* startTimes, int* finishTimes, int n )
{
    cout << \"Following activities are selected \ \";
    cout << \"Activity with start time: \" << startTimes[0] << \" and end time: \" << finishTimes[0]<<endl;
    int i = 0;
    for(int j = 1; j < n; j++){
      if( startTimes[j] >= finishTimes[i] ){
          cout << \"Activity with start time: \" << startTimes[j] << \" and end time: \" << finishTimes[j]<<endl;
          i = j;
      }
    }
    cout << endl;
}

void sortByFinishTimes( int* startTimes, int* finishTimes, int size ){
pair<int,int> arr[size];
for(int i =0; i < size; i++){
    arr[i] = make_pair( finishTimes[i], startTimes[i] );
}
sort( arr, arr + size);
for(int i =0; i < size; i++){
    finishTimes[i] = arr[i].first;
    startTimes[i] = arr[i].second;
}
}

int main()
{
    int startTimes[] = {6,4,8,1,14,11,12,14,16,4,9,8};
    int finishTimes[] = {8,9,10,5,16,12,15,17,18,7,13,12};
    int n = sizeof(startTimes)/sizeof(startTimes[0]);
    sortByFinishTimes( startTimes, finishTimes, n );
    greedyActivitySelector(startTimes, finishTimes, n);
    return 0;
}