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