Despre algoritmii Greedy

Algoritmii Greedy sunt caracterizati de metoda lor de functionare: la fiecare pas se alege cel mai bun candidat posibil, dupa evaluarea tuturor acestora. Algoritmii sunt rapizi, insa nu intotdeauna optimi. Cand nu aveti o idee mai buna legata de o problema, in timpul unui concurs, o implementare Greedy ar putea aduce in jur de 30% din punctaj.
Exista situatii in care algoritmii clacheaza, cum ar fi problema comisului voiajor, sau problemele NP-complete.

Metoda Greedy are si avantaje: poate fi aplicata multor probleme: determinarea celor mai scurte drumuri in grafuri (Dijkstra), determinarea arborelui minimal de acoperire (Prim, Kruskal), codificare arborilor Huffmann, problema spectacolelor si problema fractionara a rucsacului. Dintre acestea, articolul le trateaza numai pe ultimele doua.

Problema spectacolelor

Managerul artistic al unui festival trebuie sa selecteze o multime cat mai ampla de spectacole ce pot fi jucate in singura sala pe care o are la dispozitie.Stiind ca i s-au propus n spectacole si pentru fiecare spectacol i-a fost anuntat intervalul in care se poate desfasura [Si, Fi] (Si reprezinta ora si minutul de inceput, iar Fi ora si minutul de final al spectacolului i), scrieti un program care sa permita spectatorilor vizionarea unui numar cat mai mare de spectacole.

Date de intrare

Pe prima linie a fisierului de intrare spectacole.in se afla numarul n, numarul de spectacole propus. Pe urmatoarele n linii se vor afla 4 valori, primele doua reprezentand ora si minutul inceperii spectacolului curent, iar ultimele doua reprezentand ora si minutul terminarii spectacolului.

Date de iesire

Fisierul de iesire spectacole.out contine o singura linie, pe aceasta vor fi scrise numerele de ordine ale spectacolelor care indeplinesc solutia problemei, printr-un spatiu.

Restrictii

• n <= 100

Exemplu

Descrierea solutiei

Vom sorta crescator spectacolele dupa ora de final. Vom selecta initial primul spectacol (cel care se termina cel mai devreme). In continuare vom selecta, la fiecare pasa, primul spectacol neselectat, care nu se suprapune peste cele deja selectate.

O implementare intuitiva a acestui algoritm va fi prezentata in continuare. Pentru sortat vom folosi metoda BubbleSort, care este indeajuns de buna pentru limitele impuse de problema.

#include <iostream>
#include <fstream>
using namespace std;

ifstream f("spectacole.in");
ofstream g("spectacole.out");

int n,inceput[100],sfarsit[100],nr[100];

void citeste()
{
	int ora,min,i;
	f>>n;
	for (i=0;i<n;++i)
	{
		nr[i]=i+1;
		f>>ora>>min;
		inceput[i]=ora*60+min;
		f>>ora>>min;
		sfarsit[i]=ora*60+min;
	}
	f.close();
}

void sorteaza()
{
	int aux,schimb,i;
	do
	{
		schimb=0;
		for (i=0;i<n-1;++i)
			if (sfarsit[nr[i]]>sfarsit[nr[i+1]])
			{
				aux=nr[i];
				nr[i]=nr[i+1];
				nr[i+1]=aux;
				schimb=1;
			}
	}
	while (schimb);
}

void rezolva()
{
	int ultim,i;
	for (ultim=0,i=1;i<n;++i)
		if (inceput[nr[i]]>=sfarsit[nr[ultim]])
		{
			g<<nr[i]+1<<" ";
			ultim=i;
		}
	g<<endl;
}

int main()
{
	citeste();
	sorteaza();
	rezolva();
	return 0;
}