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

typedef struct {
   double L; /* left endpoint */
   double R; /* right endpoint */
} interval;

typedef interval *intarray; /* array of interval */

typedef struct {
   int ino;    /* interval number */
   double loc; /* x-coordinate of the endpoint */
   char type;  /* type of the endpoint: 'L' for left, 'R' for right */
} endpoint;

typedef endpoint *eparray; /* array of endpoints */

/* Generate a random array I of n subintervals of [0,1] */
void geninterval ( intarray I, int n )
{
   int i = 0;
   double L, R;

   while (i < n) {
      L = (double)rand() / (double)RAND_MAX;
      R = (double)rand() / (double)RAND_MAX;
      if (L == R) continue;
      if (L < R) { I[i].L = L; I[i].R = R; }
      else { I[i].L = R; I[i].R = L; }
      printf("Interval %6d = [%lf,%lf]\n", i, I[i].L, I[i].R);
      ++i;
   }
}

/* Compare two endpoints: Return -1 if I1 comes earlier than I2 in the
   ordering, +1 if I1 comes later than I2, 0 if I1 and I2 are equal in
   all the three fields. */
int epcmp ( endpoint I1, endpoint I2 )
{
   /* If point P1 is to the left of point P2, then P1 < P2 */
   if (I1.loc < I2.loc) return -1;
   if (I1.loc > I2.loc) return 1;

   /* We consider left endpoints of intervals earlier than right endpoints */
   if (I1.type < I2.type) return -1;
   if (I1.type > I2.type) return 1;

   /* If the locations and types of the endpoints are same, we simply compare
      the intervaal numbers. This is not a necessity. */
   if (I1.ino < I2.ino) return -1;
   if (I1.ino > I2.ino) return 1;
   return 0;
}

/* Merging two sorted arrays of endpoints */
void merge ( eparray P, int n1, int n2 )
{
   eparray Q;
   int i1, i2, j;

   Q = (eparray)malloc((n1+n2)*sizeof(endpoint));
   i1 = 0; i2 = n1; j = 0;
   while ((i1 < n1) || (i2 < n1+n2)) {
      if (i1 == n1) Q[j++] = P[i2++];
      else if (i2 == n1+n2) Q[j++] = P[i1++];
      else if (epcmp(P[i1],P[i2]) <= 0) Q[j++] = P[i1++];
      else Q[j++] = P[i2++];
   }
   for (j=0; j<n1+n2; ++j) P[j] = Q[j];
   free(Q);
}

/* Recursive function for merge sorting an endpoint array P of size n */
void msort ( eparray P, int n )
{
   int m;

   if (n == 1) return;

   m = n / 2;
   msort(P,m);
   msort(P+m,n-m);
   merge(P,m,n-m);
}

/* Input: An array I of n intervals.
   Output: The sorted list P of the 2n endpoints of the input intervals. */
void sortendpoint ( eparray P, intarray I, int n )
{
   int i;
   for (i=0; i<n; ++i) {
      P[2*i].ino = i; P[2*i].loc = I[i].L; P[2*i].type = 'L';
      P[2*i+1].ino = i; P[2*i+1].loc = I[i].R; P[2*i+1].type = 'R';
   }
   msort(P,2*n);
}

/* Find the interval of maximum overlap.
   Return the number of ingervals in the maximum-overlap zone. */
int getmaxoverlap ( interval *I, eparray P, int n )
{
   int max, cnt, i;

   max = cnt = 0;
   I->L = -1; I->R = -1;
   for (i=0; i<2*n; ++i) {      /* For each endpoint in P in sorted order */
      if (P[i].type == 'L') {   /* A new interval enters the current overlap */
         ++cnt;                 /* Increase overlap size */
         if (cnt > max) {       /* The current overlap size is larger than the previous maximum */
            max = cnt;          /* Remember the new overlap size */
            I->L = P[i].loc;    /* The overlap zone starts here */
            I->R = -1;          /* The end of the overlap zone is to be determined later */
         }
      } else {                  /* An overlapping interval ends */
         --cnt;
         if (I->R == -1)        /* A maximum-overlap zone has started just before this */
            I->R = P[i].loc;    /* The end of the current overlap is identified here */
      }
   }
   return max;
}

/* Print indices of all intervals in I that has non-empty intersection
   with the overlap zone */
void prninterval( interval overlap, intarray I, int n )
{
   int i, nprn, cnt;
   double x;

   /* Set x to the midpoint of the overlap zone. Any point in the overlap
      zone (even the endpoints) would serve our purpose. */
   x = (overlap.L + overlap.R ) / 2;

   /* for all input intervals */
   for (i=nprn=cnt=0; i<n; ++i) {
      /* if x belongs to the i-th interval */
      if ((x >= I[i].L) && (x <= I[i].R)) {
         ++cnt;
         printf("%7d",i);
         if (nprn == 0) printf("\t");
         if (++nprn == 10) {
            printf("\n");
            nprn = 0;
         }
      }
   }
   if (nprn != 0) printf("\n");

   /* Print cnt as a check for correctness */
   printf("Number of indices printed is %d\n", cnt);
}

int main ()
{
   int n;
   intarray I;
   eparray P;
   interval overlap;
   int cnt;

   srand((unsigned int)time(NULL));
   printf("How many intervals? "); scanf("%d", &n);
   if (n <= 0) {
      fprintf(stderr, "Number of intervals should be positive...\n");
      exit(1);
   }
   I = (intarray)malloc(n*sizeof(interval));
   P = (eparray)malloc(2*n*sizeof(endpoint));
   geninterval(I,n);
   sortendpoint(P,I,n);
   cnt = getmaxoverlap(&overlap,P,n);
   printf("Leftmost maximum overlap is [%lf,%lf]\n", overlap.L, overlap.R);
   printf("Number of overlapping intervals is %d\n", cnt);
   printf("Indices of overlapping intervals are:\n");
   prninterval(overlap,I,n);
   free(I); free(P);
   exit(0);
}