Si generi un programma in grado di risolvere il seguente problema, noto con il nome di interval scheduling:

  • Input: un insieme I di intervalli, rappresentati da coppie di punti (estremi dell’intervallo);
  • Output: il più grande sottoinsieme J di intervalli di I che non si sovrappongono.

È importate notare come non esista un’unica soluzione per il problema proposto, infatti, nulla impedisci l’esistenza due sottoinsiemi della stessa cardinalità formati entrambi da intervalli di S che non si sovrappongono tra loro. Il programma dovrà fornire uno qualsiasi di questi sottoinsiemi, che chiameremo ottimali.

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

#define LIMIT 11

struct evento {
  int inizio;
  int fine;
};

typedef struct evento evento;

void ordina(evento *ev);
int scelta(evento *ev, evento *ev_def);

int main(void) {
  evento ev[LIMIT];  // insieme degli eventi
  evento *ev_def;    // insieme degli eventi a cui parteciperai
  char string[6];
  int i, dim;

  for(i=0; i<LIMIT; i++) {
    printf("Evento %d (inizio fine): ", i+1);
    //scanf("%s", string);
    //sscanf(string, "%d %d", &ev[i].inizio, &ev[i].fine);

    scanf("%d", &ev[i].inizio);
    scanf("%d", &ev[i].fine);
  }

  ordina(ev);

  // DEBUG RISULTATO ORDINAMENTO
  // printf("Risultato dell'ordinamento:\n");
  // for(i=0; i<LIMIT; i++) {
  //   printf(" - (%d %d)\n", ev[i].inizio, ev[i].fine);
  // }
	
  ev_def = malloc(sizeof(evento));
  if(ev_def == NULL) {
    printf("Errore di allocazione");
    exit(1);
  }
  dim = scelta(ev, ev_def);

  printf("\nPuoi andare agli eventi:\n");
  for(i=0; i<dim; i++) {
    printf(" - (%d %d)\n", ev_def[i].inizio, ev_def[i].fine);
  }

  return 1;
}

void ordina(evento *ev) {
  int i, j;
  evento t;

  // Si ordinano tutti gli intervalli in base all'orario di fine, mettendo prima quello che finisce prima
  for(i=1; i<LIMIT; i++) {
    for(j=0; j<i-1; j++) {
      if(ev[i].fine < ev[j].fine) {
        memcpy(&t, &ev[i], sizeof(evento));
        memcpy(&ev[i], &ev[j], sizeof(evento));
        memcpy(&ev[j], &t, sizeof(evento));
      }
    }
  }
}

int scelta(evento *ev, evento *ev_def) {
  int i=0, dim=0;

  while(i<LIMIT) {
    // se non ho ancora inserito niente
    if(dim==0) {
      memcpy(&ev_def[dim], &ev[i], sizeof(evento));
      dim++;
    }
    else if(ev[i].inizio>=ev_def[dim-1].fine) {
      ev_def = realloc(ev_def, sizeof(evento)*(dim+1));
      if(ev_def == NULL) {
        printf("Errore di allocazione");
        exit(1);
      }

      memcpy(&ev_def[dim], &ev[i], sizeof(evento));
      dim++;
    }

    i++;
  }

  return dim;
}

Per maggiori informazioni circa la sintassi del linguaggio si faccia riferimento alla guida al Linguaggio C.