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

#define LEFT 1
#define RIGHT 2
#define L 0
#define R 999

typedef struct {
   int no;
   int l;
   int r;
} interval;

typedef struct {
   int intno;
   int ep;
   int which;
} endpoint;

interval *genintervals ( int n )
{
   interval *A, T;
   int i, *ep, j;

   A = (interval *)malloc(n * sizeof(interval));
   ep = (int *)malloc(1001 * sizeof(int));
   for (i=0; i<=1000; ++i) ep[i] = 0;
   A[0].l = 0; A[0].r = 50 + rand() % 51; ep[0] = ep[A[0].r] = 1;
   i = 1;
   while (1) {
      A[i].l = A[i-1].r - 1 - rand() % 20;
      A[i].r = A[i].l + 50 + rand() % 51;
      if ((A[i].r > 999) || (i == n-1)) A[i].r = 999;
      ep[A[i].l] = ep[A[i].r] = 1;
      ++i;
      if (A[i-1].r == 999) break;
   }
   while (i < n) {
      do A[i].l = rand() % 1000; while (ep[A[i].l]);
      A[i].r = A[i].l + 50 + rand() % 51;
      if ((A[i].r > 999) || (ep[A[i].r])) continue;
      ep[A[i].l] = ep[A[i].r] = 1;
      ++i;
   }
   for (i=0; i<n; ++i) {
      j = rand() % n;
      T = A[i]; A[i] = A[j]; A[j] = T;
   }
   for (i=0; i<n; ++i) {
      A[i].no = i;
      printf("%3d %3d   ", A[i].l, A[i].r);
      if (i % 8 == 7) printf("\n");
   }
   if (i % 8) printf("\n");
   free(ep);
   return A;
}

void mergesort ( endpoint *E, int n )
{
   endpoint *F;
   int n1, n2, i, j, k;

   if (n <= 1) return;
   n1 = (n + 1) / 2; n2 = n / 2;
   mergesort(E,n1);
   mergesort(E+n1,n2);
   F = (endpoint *)malloc(n * sizeof(endpoint));
   i = 0; j = n1;
   for (k=0; k<n; ++k) {
      if (j == n) F[k] = E[i++];
      else if (i == n1) F[k] = E[j++];
      else if (E[i].ep <= E[j].ep) F[k] = E[i++];
      else F[k] = E[j++];
   }
   for (k=0; k<n; ++k) E[k] = F[k];
   free(F);
}

endpoint *sortendpoints ( interval *A, int n )
{
   endpoint *E;
   int i;

   E = (endpoint *)malloc(2 * n * sizeof(endpoint));
   for (i=0; i<n; ++i) {
      E[2*i].intno = i; E[2*i].ep = A[i].l; E[2*i].which = LEFT;
      E[2*i+1].intno = i; E[2*i+1].ep = A[i].r; E[2*i+1].which = RIGHT;
   }
   mergesort(E,2*n);
   return E;
}

void moveupQ ( interval *H, int s, int *idx, int i )
{
   int p;
   interval T;

   while (i > 1) {
      p = i / 2;
      if (H[p].r >= H[i].r) break;
      T = H[i]; H[i] = H[p]; H[p] = T;
      idx[H[i].no] = i; idx[H[p].no] = p;
      i = p;
   }
}

void insertQ ( interval *H, int s, interval *A, int intno, int *idx )
{
   H[++s] = A[intno];
   idx[intno] = s;
   moveupQ(H,s,idx,s);
}

void deleteQ ( interval *H, int s, interval *A, int intno, int *idx )
{
   int i;

   i = idx[intno];
   idx[intno] = -1;
   if (i == s) return;
   H[i] = H[s--];
   idx[H[i].no] = i;
   moveupQ(H,s,idx,i);
}

void mincover ( interval *A, int n )
{
   int i, k, s, *idx, x, cnt;
   interval *H, I;
   endpoint *E;

   E = sortendpoints(A,n);

   H = (interval *)malloc((n+1) * sizeof(interval));
   idx = (int *)malloc(n * sizeof(int));
   for (i=0; i<n; ++i) idx[i] = -1;

   i = E[0].intno; I = A[i];
   H[1] = I; s = 1; idx[i] = 1; cnt = 1; x = I.r; k = 0;
   printf("    Added interval %3d [%3d,%3d]\n", I.no, I.l, I.r);

   while (x < R) {
      ++k;
      if (E[k].which == LEFT) {
         insertQ(H,s,A,E[k].intno,idx); ++s;
      } else {
         deleteQ(H,s,A,E[k].intno,idx); --s;
         if (E[k].ep == x) {
            ++cnt; I = H[1]; x = I.r;
            printf("    Added interval %3d [%3d,%3d]\n", I.no, I.l, I.r);
         }
      }
   }
   printf("    Total number of intervals = %d\n", cnt);

   free(E); free(H); free(idx);
}

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

   srand((unsigned int)time(NULL));
   if (argc > 1) n = atoi(argv[1]); else n = 100;
   printf("n = %d\n\n", n);

   A = genintervals(n);

   printf("\n+++ Finding minimum cover\n");
   mincover(A,n);

   free(A);
   exit(0);
}