Cod sursa(job #969343)

Utilizator mircea.dobreanuMircea Dobreanu mircea.dobreanu Data 4 iulie 2013 10:08:19
Problema Fractii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include<fstream>
#include<algorithm>
using namespace std;
const int MAXN=50001;
struct node
{
	int s,f;
};
node v[MAXN];
int n,sol=1;

void citire()
{
	ifstream fin("int.in");
	fin>>n;
	for (int k=0;k<n;++k)
		fin>>v[k].s>>v[k].f;
	fin.close();
}
void greedy()
{
	int i,j;
	for (i=0,j=1;j<n;++j)
	{
		if (v[j].s>=v[i].f)
		{
			i=j;
			++sol;
		}
	}
}
bool cmp(node x,node y)
{
	if (x.f<y.f)
		return true;
	if (x.f==y.f)
		if (x.s==y.s)
			return true;
		else if (x.s<y.s)
			return true;
		else
			return false;
	if (x.f>y.f)
		return false;
}
void afisare()
{
	ofstream fout("int.out");
	fout<<sol<<'\n';
	fout.close();
}
int main()
{
	citire();
	sort(v,v+n,cmp);
	greedy();
	afisare();
	return 0;
}