/*  Problema spectacolelor
		Intr-o sala, intr-o zi trebuie planificate n spectacole.
    Pentru fiecare spectacol se cunoaste intervalul de timp in care se
		desfasoara (ora de inceput , ora de sfarsit).
    Se cere sa se planifice un numar maxim de spectacole a.i. sa nu se
    suprapuna.
    Algoritmul:
    1-sortare spectacole dupa ora terminarii lor
    2-primul spectacol progarmat este cel care se termina cel mai devreme
    3-alegem primul spectacol din cele ce urmeaza in sir ultimului spectacol
    programat care incepe dupa ce s-a terminat ultimul spectacol programat
    4-daca nu s-a gasit un astfel de spectacol, algortimul se incheie,
    altfel se programeaza spectacolul gasit si algoritmul se reia de la
    pasul 3
    a=multimea initiala de spectacole
*/
#include <stdio.h>
#include <conio.h>

void main(void)
{
 int n,i,j,ora_sf,aux;
 int start[10],durata[10],a[10];
 clrscr();

 printf("Nr. de spectacole=");scanf("%d",&n);
 for (i=1;i<=n;i++)
 	{
    printf("spectacolul %d\n",i);
  	printf("ora de inceput =");scanf("%d",&start[i]);
    printf("durata =");scanf("%d",&durata[i]);
    a[i]=i;
  }
 // ordonarea spectacolelor

 	for(i=1;i<=n-1;i++)
  	for(j=i+1;j<=n;j++)
  		if (start[i]+durata[i]>start[j]+durata[j])
    	{
      	aux=start[i];start[i]=start[j];start[j]=aux;
        aux=durata[i];durata[i]=durata[j];durata[j]=aux;
        aux=a[i];a[i]=a[j];a[j]=aux;

      }
  ora_sf=start[1]+durata[1];
  printf("primul spectacol este nr %d\n",a[1]);
  i=2;
  while(i<=n)
  	{
    	if(ora_sf<=start[i])
      	{ printf("Spectacolul urmator este nr %d \n",a[i]);
        	ora_sf=start[i]+durata[i];
         }
      i++;
  }
   getch();
 }