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

/* Sorting criteria */
#define START_TIME 0
#define END_TIME 1

/* Parameters for generation of random intervals */
#define MAX_START 1000
#define MAX_LENGTH 100

typedef struct {
   unsigned int start;  /* Left end */
   unsigned int end;    /* Right end */
} interval;

/* Generate a list of n random intervals */
interval *genIntervals ( unsigned int n )
{
   interval *A;
   unsigned i;

   if (n == 0) return NULL;
   A = (interval *)malloc(n * sizeof(interval));
   for (i=0; i<n; ++i) {
      A[i].start = rand() % MAX_START;
      A[i].end = A[i].start + 1 + rand() % MAX_LENGTH;
   }
   return A;
}

/* Linear-time merge function. flag indicates whether the sorting is with
   respect to the left or the right endpoints. */
void merge ( interval *A1, unsigned int n1, interval *A2, unsigned int n2, int flag )
{
   int i1, i2, i;
   interval *B;

   B = (interval *)malloc((n1+n2) * sizeof(interval));
   i1 = i2 = i = 0;

   if (flag == START_TIME) {
      while ((i1 < n1) || (i2 < n2)) {
         if (i1 >= n1) B[i++] = A2[i2++];
         else if (i2 >= n2) B[i++] = A1[i1++];
         else if (A1[i1].start <= A2[i2].start) B[i++] = A1[i1++];
         else B[i++] = A2[i2++];
      }
   } else if (flag == END_TIME) {
      while ((i1 < n1) || (i2 < n2)) {
         if (i1 >= n1) B[i++] = A2[i2++];
         else if (i2 >= n2) B[i++] = A1[i1++];
         else if (A1[i1].end <= A2[i2].end) B[i++] = A1[i1++];
         else B[i++] = A2[i2++];
      }
   } else {
      fprintf(stderr, "*** Error in merge(): Unknown sorting criterion\n");
      free(B);
      exit(1);
   }

   for (i=0; i<n1+n2; ++i) A1[i] = B[i];
   free(B);
}

/* Recursive merge sort */
void mergeSort ( interval *A, unsigned int n, int flag )
{
   unsigned int n1, n2;

   if (n <= 1) return;
   n1 = (n >> 1); n2 = n - n1;
   mergeSort(A,n1,flag);
   mergeSort(A+n1,n2,flag);
   merge(A,n1,A+n1,n2,flag);
}

/* Print the intervals, six in a line */
void printIntervals ( interval *A, unsigned int n )
{
   int i;

   for (i=0; i<n; ++i) {
      printf("[%4u,%4u] ", A[i].start, A[i].end);
      if (i % 6 == 5) printf("\n");
   }
   if (i % 6) printf("\n");
}

/* This is the greedy schedule function, same as in Assignment 2.
   We do not need a flag here. */
void schedule ( interval *A, unsigned int n )
{
   unsigned i, j, util;
   interval *S;

   if (n == 0) return;

   S = (interval *)malloc(n * sizeof(interval));

   S[0] = A[0]; i = j = 1;

   while (1) {
      while ((i < n) && (A[i].start < S[j-1].end)) ++i;
      if (i >= n) break;
      S[j++] = A[i++];
   }

   printf("--- Total number of intervals selected = %u\n", j);
   printIntervals(S,j);
   util= 0; for (i=0; i<j; ++i) util += (S[i].end - S[i].start);
   printf("Total utilization = %u\n", util);
   free(S);
}

/* The dynamic-programming function to compute the maximum utilization */
void maxutil (interval *A, unsigned int n, int flag )
{
   unsigned int u1,      /* Used to store the cost if an interval is included */
                u2,      /* Used to store the cost if an interval is excluded */
                util,    /* Utilization computed from the selected intervals */
                x,       /* Key for binary search */
                *U;      /* U[i] stores the best utlization for intervals i through n-1 */
   interval *S;          /* Used to store the optimal schedule */
   int *V,               /* V[i] stores 0 if u2 > u1, else it stores the index of the next compatible interval */
       i, j,
       L, R, M;          /* Used in the binary search */

   if (n == 0) return;

   U = (unsigned int *)malloc(n * sizeof(unsigned int));
   V = (int *)malloc(n * sizeof(int));

   /* The smallest subproblem of one interval (the last one) */
   U[n-1] = A[n-1].end - A[n-1].start; V[n-1] = n;

   /* Iteratively solve bigger and bigger subproblems */
   i = n-2;
   for (i=n-2; i>=0; --i) {
      u1 = A[i].end - A[i].start;      /* The ith interval is included, so the
                                          length of this interval initializes u1 */
      /* Now locate the next compatible interval, if any */
      x = A[i].end; L = i+1; R = n-1;
      if (A[R].start < x) {            /* No following interval is compatible */
         L = n;
      } else {                         /* Do binary search among (i+1)st to (n-1)st intervals */
         while (L < R) {
            M = (L + R) / 2;
            if (A[M].start >= x) R = M; else L = M+1;
         }
         u1 += U[L]; 
      }
      u2 = U[i+1];                     /* The ith interval is excluded */
      if (u1 >= u2) {  /* Better utilization if the i-th interval is included */
         U[i] = u1; V[i] = L;          /* L stores the index of the next compatible interval */
      } else {         /* Better utilization if the i-th interval is excluded */
         U[i] = u2; V[i] = 0;
      }
   }

   printf("Total utilization = %u (computed by the d-p approach)\n", U[0]);

   S = (interval *)malloc(n * sizeof(interval));
   i = j = 0;
   while (i < n) {
      if (V[i]) {    /* Include the i-th interval in the schedule */
         S[j++] = A[i];  /* Append the i-th interval to the optimal schedule */
         i = V[i];       /* Change i to the index of the next compatible interval */
      } else {       /* Exclude the i-th interval from the schedule */
         ++i;            /* Search from the next index */
      }
   }

   printf("--- Total number of intervals selected = %u\n", j);
   printIntervals(S,j);
   util= 0; for (i=0; i<j; ++i) util += (S[i].end - S[i].start);
   printf("Total utilization = %u (computed from the optimal schedule)\n", util);

   /* Clean locally used memory befre leaving */
   free(U); free(V); free(S);
}

int main ( int argc, char *argv[] )
{
   unsigned int n;
   interval *A;

   srand((unsigned int)time(NULL));
   if (argc > 1) n = atoi(argv[1]); else scanf("%u",&n);
   A = genIntervals(n); printIntervals(A,n);

   printf("\n+++ Schedule 1: Earliest finish time first\n");
   mergeSort(A,n,END_TIME); printIntervals(A,n);
   schedule(A,n);

   printf("\n+++ Schedule 2: Earliest start time first\n");
   mergeSort(A,n,START_TIME); printIntervals(A,n);
   schedule(A,n);

   printf("\n+++ Schedule 3: Dynamic programming\n");
   printf("The intervals are already sorted with respect to start time\n");
   maxutil(A,n,START_TIME);

   exit(0);
}