fueanta

Greedy - Activity Selection

Oct 24th, 2017
121
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. struct Activity
  6. {
  7.     string name;
  8.     double startingTime;
  9.     double endingTime;
  10. };
  11.  
  12. void showActivities(Activity*, int, string);
  13. void takeActivityDetails(Activity*, int);
  14. void sortByEndingTime(Activity*, int);
  15. int selectActivities(Activity*, Activity*, int);
  16.  
  17. int main(void)
  18. {
  19.     cout << "How many activities? No: ";
  20.     int size; cin >> size;
  21.  
  22.     Activity* activities = new Activity[size];
  23.     takeActivityDetails(activities, size);
  24.     showActivities(activities, size, "Given");
  25.  
  26.     Activity* selected = new Activity[size];
  27.     int total = selectActivities(activities, selected, size);
  28.  
  29.     // cout << "\nTotal: " << total << endl;
  30.  
  31.     showActivities(selected, total, "Selected");
  32.  
  33.     return 0;
  34. }
  35.  
  36. void showActivities(Activity* arr, int n, string type)
  37. {
  38.     cout << endl << type << " activities:\n";
  39.     for ( int i = 0; i < n; ++i )
  40.     {
  41.         cout << "-> " << arr[i].name << " " << arr[i].startingTime << " "
  42.         << arr[i].endingTime << endl;
  43.     }
  44. }
  45.  
  46. void takeActivityDetails(Activity* arr, int n)
  47. {
  48.     for ( int i = 0; i < n; ++i )
  49.     {
  50.         cout << "\nActivity " << (i + 1) << ":" << endl;
  51.         cout << "Name: "; cin >> arr[i].name;
  52.         cout << "Start-time: "; cin >> arr[i].startingTime;
  53.         cout << "End-time: "; cin >> arr[i].endingTime;
  54.     }
  55. }
  56.  
  57. void sortByEndingTime(Activity* arr, int n)
  58. {
  59.     for (int i = 1; i <= n - 1; i++) {
  60.         int LOC = i;
  61.         Activity VAL = arr[LOC];
  62.         while (LOC > 0 && arr[LOC - 1].endingTime > VAL.endingTime) {
  63.             arr[LOC] = arr[LOC - 1];
  64.             LOC--;
  65.         }
  66.         arr[LOC] = VAL;
  67.     }
  68. }
  69.  
  70. int selectActivities(Activity* activities, Activity* selected, int size)
  71. {
  72.     int i = 0, j = 1, count = 1;
  73.     selected[0] = activities[0];
  74.     while ( j <= size )
  75.     {
  76.         if ( activities[i].endingTime <= activities[j].startingTime )
  77.         {
  78.             selected[count++] = activities[j];
  79.             i = j;
  80.         }
  81.         j++;
  82.     }
  83.     return count;
  84. }
RAW Paste Data