Saturday, July 30, 2016

The Activity Selection Problem With Greedy Algorithom

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <conio.h>

using namespace std;

struct activity{
double s;
double e;
double c;
};

bool compare(activity p1, activity p2){
if(p1.e<p2.e)
return true;
else
return false;
}

int main(){
activity p[100];
int n,i;
int start,End;
int count = 1;
scanf("%d",&n);
for(i=0;i<n;i++){
cin>>start;
cin>>End;
p[i].s = start;
p[i].e = End;
}
sort(p,p+n, compare);

int j= 0;
for(i=1; i<n; i++){
        if(p[i].s >= p[j].e){
            count ++;
            j=i;
        }
}
cout << "Activity : "<<count<<endl;

getch();
return 0;
}

No comments:

Post a Comment