Nimbus3000

main.cpp

//
//  main.cpp
//  Nimbus3000
//
//  Created by Ale on 04/03/16.
//  Copyright © 2016 ABeltramo. All rights reserved.
//

#include <iostream>
#include <fstream>

using namespace std;

struct Intervallo{
	int inizio,fine;
};

// compare_intervalli(a,b):
// dati due intervalli ritorna true se la fine di a < fine di b
// serve per ordinare automaticamente il vettore
// vedi sort(...) nel main
bool compare_intervalli(const Intervallo &a, const Intervallo &b){
	if(a.fine < b.fine)
		return true;
	return false;
}

int N;
Intervallo giri[1000];

int main() {
	ifstream in("input.txt");
	ofstream out("output.txt");
	in >> N;
	for (int i=0; i<N; i++)
	{
		in >> giri[i].inizio >> giri[i].fine;
	}
	sort(giri,giri+N,compare_intervalli); // Ordino il vettore
	int fine_attuale = giri[0].fine;
	int caramelle = 1;
	for (int i=1; i<N; i++)
	{
		if (fine_attuale < giri[i].inizio) {	// Se ne posso aggiungere un altro
                                          // fine attuale viene prima dell'inizio del successivo
			fine_attuale = giri[i].fine;
			caramelle++;
		}
	}
	out << caramelle << endl ;
	return 0;
}

testo.txt

https://www.dropbox.com/s/ucuox04ga7kjn1m/Problema.pdf?dl=0