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

typedef struct {
    int inizio;
    int fine;
} att_t;

att_t *acquisizione(int *n);
void BubbleSort(att_t *attV, int n);
int duration(att_t att);
void solve(att_t *attV,int n);
int notIntersection(att_t current_att, att_t prev_att);
void displaySol(int *opt,att_t *attV,int n);

int main() {
    att_t *vett_Att;
    int n;

    vett_Att = acquisizione(&n);            /*Creazione vettore di activities*/
    BubbleSort(vett_Att,n);
    solve(vett_Att,n);
    free(vett_Att);
    return 0;
}

att_t *acquisizione(int *n) {
    att_t *vett_AttTMP;
    FILE *fp;
    int i;
    fp = fopen("activity.txt", "r");
    if (fp == NULL) {
        printf("Errore file\n");
        exit(EXIT_FAILURE);
    }
    fscanf(fp, "%d", n);
    vett_AttTMP = malloc((*n+1) * sizeof(att_t));
    vett_AttTMP[0].inizio=0;
    vett_AttTMP[0].fine=0;
    for (i = 1; i <= *n; i++) {
        fscanf(fp, "%d %d", &vett_AttTMP[i].inizio, &vett_AttTMP[i].fine);
    }
    return vett_AttTMP;
}
void BubbleSort(att_t *attV, int n){
    int i,j;
    int l=0,r=n-1;
    att_t tmp;
    for(i=l;i<r;i++){
        for(j=0;j<r-i+l;j++){
            if(attV[j].inizio > attV[j + 1].inizio){
                /*scambio le celle*/
                tmp.inizio=attV[j].inizio;
                tmp.fine=attV[j].fine;
                attV[j].inizio=attV[j + 1].inizio;
                attV[j].fine=attV[j + 1].fine;
                attV[j + 1].inizio=tmp.inizio;
                attV[j + 1].fine=tmp.fine;
            }
        }
    }
}
int duration(att_t att){
    return (att.fine-att.inizio);
}

void solve(att_t *attV,int n){
    int i;
    int *opt;
    opt=calloc(n+1, sizeof(int));
    opt[1]=duration(attV[1]);
    for(i=2;i<=n;i++){
        if(opt[i-1] > opt[i-2]+duration(attV[i]) ){
            opt[i] = opt[i-1];
        } else if (opt[i-2]+duration(attV[i]) > opt[i-1] && notIntersection(attV[i],attV[i-2])){
            opt[i]=opt[i-2]+duration(attV[i]);
        }
    }
    printf("Dynamic Programming solution: max activities duration is %d\n",opt[n]);
    displaySol(opt,attV,n);
    free(opt);
}
int notIntersection(att_t current_att, att_t prev_att){
    if(current_att.inizio<prev_att.fine){
        /*C'è intersezione*/
        return 0;
    }
    return 1;
}
void displaySol(int *opt,att_t *attV,int n){
    int i,*sol;
    sol=calloc(n+1, sizeof(int));
    sol[1]=1;
    i=n;
    while (i>=2){
        if(opt[i]==opt[i-1]){
            sol[i]=0;
            i--;
        }
        else if(opt[i]==opt[i-2]+duration(attV[i])){
            sol[i]=1;
            sol[i-1]=0;
            i-=2;
        }
    }
    for(i=0;i<=n;i++){
        printf("Activity %d: %d\n",i,sol[i]);
    }
    for(i=1;i<n+1;i++){
        if(sol[i]){
            printf("(%2d,%2d)\n",attV[i].inizio,attV[i].fine);
        }
    }
    free(sol);
}