nr max de intervale neintersectate greedy

// Se dau N intervale inchise. Sa se determine un numar maxim de intervale care nu se intersecteaza 2 cate 2

#include <stdio.h>
#include <stdlib.h>

struct interval
{
    int start, finish;
};

void citire(FILE *fin,int *n, struct interval *ptr)
{
    fscanf(fin,"%d",&(*n));
    int i;

    for (i=0; i<*n; i++)
    {
        fscanf(fin,"%d %d",&ptr->start,&ptr->finish);
        ptr++;
    }

}

void afisare(FILE *fout, int n, struct interval *ptr)
{
    fprintf(fout,"Vector sortat:\n");

    int i;

    fprintf(fout,"%d\n",n);

    for (i=0; i<n; i++)
    {
        fprintf(fout,"%d %d\n", ptr->start, ptr->finish);
        ptr++;
    }

}

void sortare(int n, struct interval *v) //sortare cu complexitate n^2
{
    int i,j;
    struct interval aux;

    for (i=0; i<n; i++)
        for (j=i+1; j<n; j++)
            if (v[i].finish > v[j].finish)
                {
                    aux = v[i];
                    v[i] = v[j];
                    v[j] = aux;
                }

}

int comparator(const void *s1, const void *s2) //asta e pentru quicksort
{
    struct interval *e1 = (struct interval *) s1;
    struct interval *e2 = (struct interval *) s2;

    return e1->finish - e2->finish;
}

void greedy(FILE *fout, int n, struct interval *v)
{
    fprintf(fout,"\n********************************************************\nRezolvare:\n");
    fprintf(fout,"%d %d\n",v[0].start,v[0].finish);

    int lastTime = v[0].finish, i = 1;

    while (i < n)
    {
        if (v[i].start > lastTime)
        {
            lastTime = v[i].finish;
            fprintf(fout,"%d %d\n",v[i].start,v[i].finish);
        }
        i++;
    }
}

int main()
{
    FILE *fin, *fout;

    fin = fopen("date.in","r");
    fout = fopen("date.out","w");

    struct interval vec[100];
    int n;

    citire(fin,&n,vec);
    //sortare(n,vec); //are n^2, e mai proasta ca quicksort
    qsort(vec,n,sizeof(struct interval),comparator);
    afisare(fout,n,vec);
    greedy(fout,n,vec);

    return 0;
}