#include #include #include 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; jL = -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= 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); }