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

#define NDAYS 30
#define LONGEST 10
#define NREQ 25

void genReq ( int start[], int finish[], int n )
{
   int i, s, f;

   srand((unsigned int)time(NULL));

   i = 0;
   while (i < n) {
      s = 1 + rand() % NDAYS;
      f = s + rand() % LONGEST;
      if (f <= NDAYS) {
         start[i] = s;
         finish[i] = f;
         ++i;
      }
   }
}

void sortReq ( int start[], int finish[], int n )
{
   int i, j, t;

   for (j=n-2; j>=0; --j) {
      for (i=0; i<=j; ++i) {
         if (start[i] > start[i+1]) {
            t = start[i]; start[i] = start[i+1]; start[i+1] = t;
            t = finish[i]; finish[i] = finish[i+1]; finish[i+1] = t;
         }
      }
   }
}

void printReq ( int start[], int finish[], int next[], int n )
{
   int i;

   for (i=0; i<n; ++i)
      printf("Request %2d: %2d -- %2d (%2d)\n", i, start[i], finish[i], next[i]);
}

void getNext ( int start[], int finish[], int next[], int n )
{
   int i, j;

   for (i=0; i<n; ++i) {
      j = i + 1;
      while ((j < n) && (start[j] <= finish[i])) ++j;
      next[i] = j;
   }
}

void genSchedule ( int start[], int finish[], int next[], int n )
{
   int serve[NREQ], best[NREQ], i, util1, util2;

   serve[n-1] = 1; best[n-1] = finish[n-1] - start[n-1] + 1;
   for (i=n-2; i>=0; --i) {
      if (next[i] < n)
         util1 = (finish[i] - start[i] + 1) + best[next[i]];
      else
         util1 = finish[i] - start[i] + 1;
      util2 = best[i+1];
      if (util1 >= util2) {
         best[i] = util1;
         serve[i] = 1;
      } else {
         best[i] = util2;
         serve[i] = 0;
      }
   }

   printf("Recommended schedule: ");
   i = 0;
   while (i < n) {
      if (serve[i]) {
         printf("%d ", i);
         i = next[i];
      } else {
         ++i;
      }
   }
   printf("\n");
   printf("Total utilization: %d\n", best[0]);
}

int main ()
{
   int start[NREQ], finish[NREQ], next[NREQ];

   genReq(start,finish,NREQ);
   sortReq(start,finish,NREQ);
   getNext(start,finish,next,NREQ);
   printReq(start,finish,next,NREQ);
   genSchedule(start,finish, next,NREQ);
   exit(0);
}