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