C++ greedy algorithm implementation activity scheduling problem of instance code

Greedy algorithm

The greedy algorithm (also known as the greedy algorithm) always makes the best choice for solving a problem. In other words, instead of considering it from the perspective of global optimality, what he does is to some extent a local optimal solution.

Greedy algorithm can not get the overall optimal solution for all problems, but the key is the selection of greedy strategy. The selected greedy strategy must have no aftereffect, that is, the process before a certain state will not affect the future state, but is only related to the current state.

The specific code is as follows:

#include <cstdio>
#include <iostream>
#include <ctime>
#include <windows.h>
#include <algorithm>
#include <fstream>
using namespace std;
struct activity
{
  int no;
  int start;
  int finish;
};
bool cmp(const activity &x, const activity &y)
{
  return x.finish<y.finish;// From small to big < If you want to go from big to small >
}
int greedySelector(int m,int solution[],struct activity activity[]){
  int number = 1;
  solution[0] = 1;
  int i,j = 0,counter = 1;
  for(i = 1;i < m ;i++)
  {
    if(activity[i].start >=activity[j].finish)
    {
      solution[i] = 1;
      j = i;
      counter++;
    }
    else
      solution[i] = 0;
  }
  cout << "The amount of activities is:"<<counter<<endl;
  cout << "The solution is:";
  for(i = 0 ;i < m ;i++)
  {
    if (solution[i] == 1)
    {
      cout << activity[i].no <<" ";
    }
  }
  return counter;
}
int main(void)
{
  LARGE_INTEGER nFreq;
  LARGE_INTEGER nBeginTime;
  LARGE_INTEGER nEndTime;
  ofstream fout;
  srand((unsigned int)time(NULL));
  int m,i,j,t;
  double cost;
  cout << "Please enter the number of times you want to run the program:";
  cin >> t;
  fout.open("activity.txt",ios::app);
  if(!fout){
    cerr<<"Can not open file 'activity.txt' "<<endl;
    return -1;
  }
  fout.setf(ios_base::fixed,ios_base::floatfield);    // Prevent output Numbers from using scientific counting 
  for (j = 0;j < t;j++)
  {
    cout << " -- -- -- -- -- -- -- -- -- The "<< j + 1 << "th test  -- -- -- -- -- -- -- -- - "<<endl;
    m = 1 + rand()%100000;
    fout<<m<<",";
    int solution[m];
    activity activity[m];
    for( i = 0;i < m;i++)
    {
      activity[i].no = i+1;
      activity[i].start = 1 + rand()%1000;
      while(1)
      {
        activity[i].finish = 1 + rand()%10000;
        if(activity[i].finish > activity[i].start) break;
      }
    }
    QueryPerformanceFrequency(&nFreq);
    QueryPerformanceCounter(&nBeginTime);
    sort(activity,activity+m,cmp);
    greedySelector(m,solution,activity);
    QueryPerformanceCounter(&nEndTime);
    cost=(double)(nEndTime.QuadPart - nBeginTime.QuadPart) / (double)nFreq.QuadPart;
    fout << cost << endl;
    cout << "\nThe running time is:" << cost << " s" << endl;
  }
  fout.close();
  cout << endl << endl;
  cout << "Success!" << endl;
  return 0;
}

conclusion